графы - Докажите, что из клуба можно исключить 33 джентльмена

Рассмотрим граф знакомств. Пусть в нём имеется треугольник ABC. Возможны два случая.

Первый: ни один из джентльменов A, B, C не входит ни в какую другую из троек. Тогда выделяем джентльмена A, который подлежит удалению, и отмечаем джентльменов B, C, которых мы хотим оставить.

Второй случай: джентльмен A входит ещё в какую-то тройку. Поскольку у него помимо B и C может быть только один знакомый D, то он входит в тройку с D и одним из B, C. Для определённости пусть это будет тройка ABD. У нас возникло два треугольника ABC и ABD с общим ребром. Согласно условию, C и D не знакомы (поскольку все остальные в четвёрке A, B, C, D знакомы). Легко видеть, что в этом случае никто из четверых не может входить более ни в какую из троек. Для A и B это очевидно, так как трое их знакомых уже налицо, и там дополнительной тройки больше нет. Если C знаком с кем-то третьим помимо A и B, скажем, с E, то он с ним в одну тройку не войдёт, так как E не знаком ни с A, ни с B. Аналогично для D.

Теперь выделяем A, подлежащего удалению, а каждого из B, C, D оставляем. Просматривая все треугольники, мы выделяем одного, и оставляем двух или трёх. Все рассмотренные подмножества (тройки и четвёрки) попарно не пересекаются. Теперь мы можем исключить тех, кого наметили, и это будет не более 1/3 от всех, то есть не более 33. Далее исключим ещё несколько человек, чтобы их стало ровно 33. В оставшемся подмножестве треугольников уже не будет, так как каждому из имевшихся в начале треугольников соответствует одна исключаемая вершина.