Рассмотрим вариант решения задания из учебника Мерзляк, Полонский, Якир 6 класс, Вентана-Граф: 1150. В стране Севентаун семь городов, каждый из которых соединён дорогами более чем с двумя городами. Докажите, что из любого города можно доехать до любого другого (возможно, проезжая через другие города). Докажем, что, если каждый из семи городов соединён дорогами более, чем с двумя городами, всегда из любого города можно доехать до любого другого. Используем для этого метод от противного. Предположим, что при таких условиях существуют два таких города А и В, что добраться из города А в город В нельзя. По условию задачи, каждый из этих городов имеет минимум по три дороги, идущие в другие города. Чтобы было невозможно добраться из А в В, нам нужно, чтобы «соседи» города А были не соединены с «соседями» города В. Кроме того, из каждого города выходит минимум по три дороги, поэтому карта страны Севентаун будет выглядеть так. Теперь выполнены все условия, кроме самого главного: в городе не семь, а восемь городов. Наличие восьмого города позволяет получить противоречие условию задачи. Значит, наше предположение, что существуют два города А и В, между которыми нет дорожного сообщения, - неверно. Получаем, что таких городов не существует. Следовательно, из любого города можно доехать до любого другого. Для карты Севентауна это будет означать, что один город должен совпасть, например, так.
