Принцип крайнего

Будем называть не враждующих детей друзьями. Раз у каждого не больше врагов, то у каждого хотя бы друзей и из них хотя бы — не его одноклассники. Выберем пару из ученика и класса, в котором тот не учится, так, чтобы количество знакомых у этого ученика в выбранном классом было наибольшим (среди всех указанного вида). Назовем такого ученика Васей, пусть он учится в классе А, выбран класс Б, где у него друзей, а в В классе друзей, рассмотрим одного из них — Петю.

Отметим, что поскольку а в классах по учеников, то (и такой Петя найдется). Если условие не выполнено, то у Пети в Б классе не более (иначе вместе с Васей у них в этом классе есть общий друг). Значит, в А классе у Пети хотя бы друг, противоречие с выбором, который был ранее сделан.