Двудольные графы и переформулировки к ним

Рассмотрим граф с вершинами в клетках фигуры и ребрами между соседними клетками. Заметим, что наш граф имеет две доли — черные клетки и белые клетки. По условию граф связен. Значит, ребер не меньше, чем . У каждого ребра ровно один конец белый. Причем каждая белая клетка может быть концом не более чем 4 ребер (поскольку она имеет не более 4 черных соседей в нашей фигуре). Тогда белых клеток не меньше, чем , то есть не меньше . Тогда черных клеток не больше 75. Пример стоится последовательным добавлением вертикальных фигур из 4 клеточек