Упр.1150 ГДЗ Мерзляк Полонский 6 класс (Математика)

Ниже вариант решения задания из учебника Мерзляк, Полонский, Якир 6 класс, Вентана-Граф:

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

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

Используем для этого метод от противного. Предположим, что при таких условиях существуют два таких города А и В, что добраться из города А в город В нельзя.

По условию задачи, каждый из этих городов имеет минимум по три дороги, идущие в другие города. Чтобы было невозможно добраться из А в В, нам нужно, чтобы «соседи» города А были не соединены с «соседями» города В.

Кроме того, из каждого города выходит минимум по три дороги, поэтому карта страны Севентаун будет выглядеть так.

Теперь выполнены все условия, кроме самого главного: в городе не семь, а восемь городов.

Наличие восьмого города позволяет получить противоречие условию задачи. Значит, наше предположение, что существуют два города А и В, между которыми нет дорожного сообщения, - неверно. Получаем, что таких городов не существует. Следовательно, из любого города можно доехать до любого другого.

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