Задача 1:

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

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

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

Задача 2:

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

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

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

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