Теорема Эрдеша-Секереза.
В ЧУМе из mn+1 элемента есть либо цепь из n+1 элемента, либо антицепь из m+1 элемента.
Доказательство.
Возьмем множество всех минимальных элементов. Из их определения следует, что они образуют независимое множество. Удалим это минимальное множество со всеми инцидентными ему ребрами. Будем проделывать данную операцию, пока в ЧУМе остаются вершины. Вернемся к исходному ЧУМу и отметим все независимые множества, удаленные в какой-то операции. Заметим, что все эти независимые множества не пересекаются и содержат в объединении все элементы ЧУМа. Назовем независимое множество, полученное на i-ой операции i-ым ярусом. Тогда, по принципу Дирихле, есть либо антицепь из m+1 элемента, либо независимых множеств не менее n+1. Т.к. на каждом шаге (операции) мы выбирали множество всех минимальных элементов в полученном ЧУМе, то из любой вершины j-го яруса есть хотя бы одно ребро в j+1 ярус (если j-ый ярус не является последним). Таким образом есть либо цепь из n+1 элемента, либо антицепь из m+1 элемента.