Страница 19 номер 38, ГДЗ по математике за 7, 8 и 9 класс к учебнику Высоцкого 2 часть. Углубленный уровень
Из графа к задаче про три дома и три колодца (рис. 31, б) удалите одно ребро. Докажите, что получился планарный граф.
Обозначим дома Д1, Д2, Д3 и колодцы К1, К2, К3 и удалим, например, ребро Д3К1. В графе трёх домов и трёх колодцев каждый дом соединён ребром с каждым колодцем, поэтому все рёбра равноправны: какое бы ребро ни удалили, дом на его конце можно назвать Д3, а колодец — К1. После удаления ребра Д3К1 остаются 8 рёбер: Д1К1, Д1К2, Д1К3, Д2К1, Д2К2, Д2К3, Д3К2, Д3К3.
Изобразим этот граф так: вершины стоят по кругу в порядке Д1, К1, Д2, К2, Д3, К3; рёбра Д1К1, К1Д2, Д2К2, К2Д3, Д3К3, К3Д1 — стороны шестиугольника, ребро Д1К2 — отрезок внутри него, ребро Д2К3 — дуга снаружи.
Внутри шестиугольника одно ребро и снаружи одно, поэтому рёбра не имеют общих точек, кроме вершин, и граф плоский. Значит, граф, который получается из графа трёх домов и трёх колодцев удалением одного ребра, планарный.
Ответ: граф трёх домов и трёх колодцев без одного ребра планарный.
