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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. Ребра любого дерева, содержащего четное число вершин, можно покрасить в черный цвет так, чтобы для каждой вершины количество инцидентных ей черных ребер была нечетно.

Доказательство. Выберем произвольную вершину дерева и подвесим граф за нее. На шаге нашего алгоритма для каждой вершины -того с конца ранга будем красить инцидентное ей ребро в вершину высшего ранга в черный цвет, если число инцидентных ей черных ребер на данный момент четно. Так мы сможем сделать до тех пор, пока не дойдем до корня дерева. Оно уже будет удовлетворять требуемым условиям, поскольку для графа на черных ребрах выполнена лемма о рукопожатиях.