26. Хозяева трёх домов хотят выкопать три колодца, чтобы от каждого дома к каждому колодцу шла отдельная дорожка и эти дорожки не пересекались. Получится ли так сделать? (рис.)

Домам соответствуют три вершины одного множества, колодцам — три вершины другого. Дорожки должны соединить каждую пару «дом — колодец», всего требуется 3·3 = 9 дорожек. Это граф K₃,₃.

В планарном двудольном графе без мостов число рёбер не превосходит 2V − 4. Здесь V = 6, поэтому допустимо не более 2·6 − 4 = 8 рёбер. Девять дорожек без пересечений провести нельзя.

Ответ: нет, так сделать невозможно.