Задача о трёх домиках и трёх колодцах — классическая математическая головоломка: проложить от каждого из трёх колодцев к каждому из трёх домиков непересекающиеся тропинки. Формулировка задачи приписывается Эйлеру. В современной литературе иногда встречается в следующей форме: возможно ли к каждому из трёх домиков проложить без пересечений на плоскости трубы (рукава) от трёх источников — электроснабжения, газоснабжения и водоснабжения («вода, газ, электричество»).

Головоломка не имеет решения: топологическая теория графов, изучающая вложение графов в поверхности, даёт отрицательный ответ на вопрос о возможности изобразить соответствующий граф на плоскости без пересечений рёбер.

Полный двудольный граф {\displaystyle K_{3,3}}, представляющий задачу, называют «домики и колодцы», «коммунальный граф», граф Томсена.

В терминах теории графов задача сводится к вопросу о планарности полного двудольного графа К _3,3{\displaystyle K_{3,3}}. Этот граф эквивалентен циркулянтному графу С_i6 (1, 3){\displaystyle Ci_{6}(1,3)}. Казимир Куратовский в 1930 году доказал, что К_{3,3{\displaystyle K_{3,3}}} непланарен, а потому задача не имеет решения.

Одно из доказательств невозможности найти плоское вложение {\displaystyle K_{3,3}} использует разбор случаев, привлекая теорему Жордана, рассматриваются различные возможности расположения вершин по отношению к циклам длины 4 и показывается, что они несовместимы с требованием планарности. Также можно показать, что для любого двудольного планарного графа без мостов с {\displaystyle n} вершинами и {\displaystyle m} рёбрами {\displaystyle m\leqslant 2n-4}, если скомбинировать формулу Эйлера {\displaystyle n-m+f=2} (здесь f{\displaystyle f} — число граней планарного графа) с наблюдением, что число граней не превышает половины числа рёбер (поскольку любая грань имеет не менее четырёх рёбер и каждое ребро принадлежит ровно двум граням). При этом в графе {\displaystyle K_{3,3}}: К3,3: m=9 и 2n-4=8,  {\displaystyle m=9}  что нарушает неравенство, так что этот граф не может быть планарным.

Неразрешимость задачи непосредственно следует из каждой из следующих важных теорем о планарных графах: теоремы Куратовского, согласно которой планарные графы — это в точности те графы, которые не содержат подграфов, гомеоморфных {\displaystyle K_{3,3}} и полному графу {\displaystyle K_{5}}, и теоремы Вагнера о том, что планарные графы — это в точности те графы, которые не содержат ни {\displaystyle K_{3,3}}, ни {\displaystyle K_{5}} в качестве минора, содержат в себе этот результат.

По материалам:

https://ru.wikipedia.org/wiki/%D0%94%D0%BE%D0%BC%D0%B8%D0%BA%D0%B8_%D0%B8_%D0%BA%D0%BE%D0%BB%D0%BE%D0%B4%D1%86%D1%8B