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

   Решение

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

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

Прислать комментарий

Условие

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

Решение

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

Ответ

Верно.

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