Задача 14:

В стране Семерка 15 городов, каждый из которых соединен дорогами не менее, чем с 7 другими. Докажите, что из любого города можно добраться до любого другого (возможно, проезжая через другие города).

Решение:

Рассмотрим два произвольных города и предположим, что они не соединены путем, то есть такой последовательностью дорог, в которой начало очередной дороги совпадает с концом предыдущей. Каждый из этих двух городов по условию соединен не менее, чем с 7 другими; при этом все упомянутые города различны – ведь если какие-то два из них совпадают, то есть путь, соединяющий исходные города.

Таким образом, мы указали не менее 16 городов. Противоречие.

Задача 15:

Докажите, что граф с n вершинами, степень каждой из которых не менее (n – 1)/2, – связен.

Решение:

Рассмотрим две произвольных вершины и предположим, что они не соединены путем, то есть такой последовательностью ребер, в которой начало очередного ребра совпадает с концом предыдущего. Каждая из этих двух вершин по условию соединена не менее, чем с (n – 1)/2 другими; при этом все упомянутые вершины различны – ведь если какие-то две из них совпадают, то есть путь, соединяющий исходные вершины.

Таким образом, мы указали не менее вершин. Противоречие.

Задача 16:

В Тридевятом царстве лишь один вид транспорта – ковер-самолет. Из столицы выходит 21 ковролиния, из города Дальний – одна, а из всех остальных городов – по 20. Докажите, что из столицы можно долететь в Дальний (возможно, с пересадками).

Решение:

Рассмотрим компоненту связности графа ковролиний, содержащую столицу. Нам нужно доказать, что она содержит также и город Дальний. Предположим противное. Тогда в этой компоненте связности из одной вершины (столицы) выходит 21 ребро, а из всех остальных вершин – по 20 ребер. Таким образом в этом графе (компоненте связности) ровно одна нечетная вершина. Противоречие!

Задача 17:

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

Решение:

Если закрыта дорога AB, то нам достаточно доказать, что и после этого можно добраться из A в B. Если это не так, то в компоненте связности, содержащей A, все вершины, кроме A, – четные. Но наличие ровно одной нечетной вершины противоречит теореме о числе нечетных вершин.