Задание 9. У отца было 3 сына, каждый из них построил себе на общем квадратном участке дом и калитку в заборе — на рисунке 20 они отмечены одинаковыми цифрами. Два брата построили свои дома на некотором расстоянии от забора, а третий — вплотную к нему. После ссоры они решили проложить дорожки от своих калиток к домам так, чтобы они нигде не пересекались. Смогут ли они это сделать?

По рисунку каждая калитка должна быть соединена дорожкой с домом с тем же номером. Два дома находятся внутри участка, а третий примыкает к забору. Независимо от этого расположения, требование сводится к соединению каждой из трёх калиток с соответствующим домом; в показанной конфигурации это задача о непересекающемся вложении трёх попарно соединённых пар, то есть K₃,₃.

Граф K₃,₃ непланарен. Следовательно, провести все три дорожки без пересечений невозможно.

Ответ: нет.