Пусть <tex>1 \le k \le 2m</tex>. Тогда множество <tex>M</tex> с функцией приспособленности <tex>k</tex> содержит не менее <tex>k/2</tex> элементов.
|proof=
Во В множестве <tex>M</tex> каждая вершина, не имеющая пары, является крайней в некотором пути. Таким образом, каждому отдельному пути в <tex>M</tex> соответсвует пара вершин, поэтому
