Подвешивание, ранжирование, упорядочивание в графах

Будем говорить в терминах графа — либо найдётся вершина степени хотя бы , либо независимое множество размера . Пусть степень каждой вершины не больше . Выберем человека , он не знаком хотя бы с другими, поэтому достаточно найти независимое множество размера на них. Теперь выберем произвольную вершину из этих . Она соединена не более, чем с тремя из них, потому достаточно показать, что среди оставшихся найдутся две, между которыми нет ребра, что очевидно, поскольку любая из них имеет степень меньше , то есть в качестве берём любую из пяти, а в качестве ту, с которой не знаком.