Лемма о рукопожатиях

Заметим, что у каждого гостя есть хотя бы по три знакомых интроверта, поэтому интроверты точно есть. Но посмотрим на любого интроверта: у него должно быть хотя бы три знакомых интроверта, но при этом не более трёх знакомых всего (больше у интроверта быть не может). Значит, у каждого интроверта ровно три знакомых, причём все они также интроверты.

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

Осталось привести пример с интровертами. Давайте расположим всех их в вершинах правильного -угольника и проведём его главные диагонали. То есть интроверт в каждой из вершин будет соединён с соседями и противоположной вершиной.

Замечание. Однако при нечётном количестве участников вечеринке пример не удаётся построить, поскольку графа с нечётным количеством вершин нечётной степени не существует по лемме о рукопожатиях.