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

Представим учеников и отношение знакомства в виде графа. Найдем вершину наибольшей степени . Пусть вершина инцидентна и имеет наибольшую степень среди остальных вершин-соседей . Если , то по принципу Дирихле найдутся две вершины с одинаковой степенью, а у них есть общая вершина — , противоречие. Поскольку максимально, то . Итак, у нас ровно вершин, причем их степени различны и не превосходят , следовательно, они пробегают все значения от до . Вершина степени и является искомой.