Задача 30418

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

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

Условие

В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединён ровно с пятью другими?

Решение

Предположим, что это возможно. Рассмотрим тогда граф, вершины которого соответствуют телефонам, а рёбра – соединяющим их проводам. В этом графе 15 вершин, степень каждой из которых равна 5. Подсчитаем количество рёбер в этом графе. Для этого сначала просуммируем степени всех его вершин. Ясно, что при таком подсчёте каждое ребро учтено дважды (оно ведь соединяет две вершины!). Поэтому число рёбер графа должно быть равно  15·5 : 2.  Но это число нецелое! Следовательно, такого графа не существует, а значит, и соединить телефоны требуемым образом невозможно.

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

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