Quote
Вообще известно, что граф К_3,3 не является планарным, т.е. его нельзя изобразить на плоскости без самопересечений.
Известная задача «Три дома - три колодца».
Доказательство.
Пусть дорожки можно провести.
Раз задача декларируется, как геометрическая, о графах говорить не будем.
Тогда дома и колодцы – вершины многогранника(В), дорожки – ребра (Р), области, на которые разбивается плоскость – грани многогранника Г. Причем каждая грань не менее, чем четырехугольная.
По формуле Эйлера
В-Р+Г=2
У нас В=6, Р=9
Тогда Г=5.
Каждое ребро входит в 2 грани. У каждой из 5 граней не менее 4 ребер, всего ребер нужно не менее 5*4/2=10, а у нас их девять.
Дорожки провести нельзя.
