Граф  является, как и все другие полные двудольные графы, хорошо покрытым, что означает, что все наибольшие независимые множества в этом графе имеют один и тот же размер. В этом графе имеется только два наибольших независимых множества — это доли двудольного графа, и очевидно, что они равны — это один из семи 3-регулярных 3-связных хорошо покрытых графов[4].

Граф является ламановым, что означает, что он образует минимальную структурную жёсткость[en], когда он вкладывается в плоскость (с пересечениями). Это пример минимального ламанова графа, в то время как другой непланарный граф не является минимально жёстким.

 является тороидальным, что означает возможность вложить его в тор. Эквивалентным утверждением является равенство рода графа единице, откуда следует, что он не может быть вложен в поверхность с родом меньше единицы. Поверхность с родом равным единице эквивалентна тору.

В частности головоломка про домики и колодцы имеет решение на поверхности кружки (такие кружки даже можно увидеть в продаже).

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

Граф  является, как и все другие полные двудольные графы, хорошо покрытым, что означает, что все наибольшие независимые множества в этом графе имеют один и тот же размер. В этом графе имеется только два наибольших независимых множества — это доли двудольного графа, и очевидно, что они равны — это один из семи 3-регулярных 3-связных хорошо покрытых графов[4].

Граф является ламановым, что означает, что он образует минимальную структурную жёсткость[en], когда он вкладывается в плоскость (с пересечениями). Это пример минимального ламанова графа, в то время как другой непланарный граф не является минимально жёстким.

 является тороидальным, что означает возможность вложить его в тор. Эквивалентным утверждением является равенство рода графа единице, откуда следует, что он не может быть вложен в поверхность с родом меньше единицы. Поверхность с родом равным единице эквивалентна тору.

В частности головоломка про домики и колодцы имеет решение на поверхности кружки (такие кружки даже можно увидеть в продаже).

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

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

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