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

Для произвольной диаграммы Юнга рассмотрим доминошки, которые можно удалить, не потеряв корректности диаграммы. Для такой пары клеток верно, что сверху и справа от нее нет клеток. Заметим, что если две такие доминошки не пересекаются, то мы можем их удалить последовательно и получить одну и ту же диаграмму. А пересекаются они только в угле, как на картинке. Тогда удалим удалим квадрат двумя способами: при помощи удаления двух вертикальных доминошек и при помощи двух горизонтальных доминошек, и получим одну и ту же диаграмму Юнга.

Рассмотрим граф состояний диаграмм Юнга с переходами в виде удаления доминошек, так как клеток конечное число, то все пути конечны, а по доказанному выше он удовлетворяет Diamond-лемме, значит, конечное состояние — единственно.