Задача 30424

Темы:    [ Степень вершины ] [ Четность и нечетность ]

Сложность: 2+ Классы: 6,7,8

Условие

Джон, приехав из Диснейленда, рассказывал, что там на заколдованном озере имеются семь островов, с каждого из которых ведет один, три или пять мостов. Верно ли, что хотя бы один из этих мостов обязательно выходит на берег озера?

Решение

Если бы ни один мост не выходил на берег, то в соответствующем графе было бы семь нечётных вершин, что противоречит задаче 87972 б).

Ответ

Верно.

Источники и прецеденты использования

книга
Автор	Генкин С.А., Итенберг И.В., Фомин Д.В.
Год издания	1994
Название	Ленинградские математические кружки
Издательство	Киров: "АСА"
Издание	1
глава
Номер	6
Название	Графы-1
Тема	Теория графов
задача
Номер	011