Индукция в графах и теорема Турана

Индукцией по докажем утверждение задачи для любого ладейно связного множества состоящего из клеток. Клетками далее называем клетки множества База очевидна.

Шаг индукции. Будем называть пары клеток, лежащих в одной строке или в одном столбце, доминошками. Удалим какую-нибудь доминошку, состоящую, для определенности, из клеток и лежащих в одном столбце. Останется множество клеток Две клетки назовём связанными в если от одной из них до другой можно дойти ладьёй по клеткам из

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

Ясно, что Кроме того, остаётся связным при добавлении клетки — при добавлении клетки а — при добавлении любой из этих двух клеток.

Если все три множества состоят из чётного числа клеток, применим предположение индукции к этим множествам, а потом добавим доминошку

Если, скажем, в множествах и количества клеток нечётны, то эти множества непусты и количество клеток в каждом из них не превосходит а количество клеток в множестве чётно и не превосходит Тогда можно применить предположение индукции к множествам и Остальные случаи чётности разбираются аналогично.