Задача 5:

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

Решение:

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

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

Задача 6:

В государстве 100 городов, и из каждого из них выходит 4 дороги. Сколько всего дорог в государстве?

Решение:

Общее число дорог равно 100 • 4/2 = 200.

Задача 7:

В классе 30 человек. Может ли быть так, что 9 из них имеют по 3 друга (в этом классе), 11 – по 4 друга, а 10 – по 5 друзей?

Решение:

Если бы это было возможно, то можно было бы нарисовать граф с 30 вершинами, 9 из которых имели бы степень 3, 11 – степень 4, 10 – степень 5. Однако у такого графа 19 нечетных вершин, что противоречит теореме.

Задача 8:

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

Решение:

Нельзя. Примените теорему о числе нечетных вершин.

Задача 9:

У короля 19 баронов-вассалов. Может ли оказаться так, что у каждого вассального баронства 1, 5 или 9 соседних баронств?

Решение:

Нет, не может. В противном случае получился бы граф соседства баронств с нечетным количеством нечетных вершин.

Задача 10:

Может ли в государстве, в котором из каждого города выходит 3 дороги, быть ровно 100 дорог?

Решение:

Если в государстве k городов, то дорог – 3k/2. Это число не может быть равно 100.

Задача 11:

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

Решение:

Да, верно, иначе нарушается теорема о числе нечетных вершин.

Задача 12:

Докажите, что число людей, когда-либо живших на Земле и сделавших нечетное число рукопожатий, четно.

Решение:

Это в точности теорема о нечетных вершинах.

Задача 13:

Можно ли нарисовать на плоскости 9 отрезков так, чтобы каждый пересекался ровно с тремя другими?

Решение:

Нет, нельзя. Примените теорему к графу, вершины которого – данные отрезки, а ребро соединяет две вершины тогда, когда два соответствующих отрезка пересекаются.