Увидеть граф (переформулировки)

Рассмотрим граф, вершинами которого являются вершины прямоугольников, и две вершины графа соединены ребром тогда и только тогда, когда они являются диагонально-противоположными вершинами одного из прямоугольников разбиения.

Из условия задачи вытекает, что степень каждой вершины графа — или При этом вершин степени — четыре штуки, это и поэтому наш граф представляет собой объединение путей и циклов, причём путей в нем ровно Кроме того, все циклы имеют чётную длину, так как по условию цвета вершин в циклах чередуются. Поскольку общее число ребер графа чётно (оно равно удвоенному числу прямоугольников разбиения), и в каждом цикле чётное число ребер, то в двух путях в сумме чётное число ребер. В двух путях цвета вершин тоже чередуются.

Есть две возможности.

Два пути — это и По условию один из этих путей имеет нечётное число ребер, поэтому второй — тоже. Это и требовалось доказать.

Два пути — это и (и аналогичный случай и По условию и имеют одинаковые цвета, поэтому другие концы путей (то есть и одинаковой чётности тоже имеют одинаковые цвета.