Допустим противное - четырёх попарно знакомых нет. Тогда справедливы следующие утверждения.
Лемма 1. У каждого жителя не более
знакомых с ним жителей.Доказательство. Если бы это было не так и у какого-то жителя нашлось бы

знакомых, то, т.к. среди них есть тройка попарно знакомых, то эта тройка вместе с исходным жителем образовала бы четвёрку попарно знакомых.
Лемма 1. Если
, где
, то в любой группе из
жителей города найдётся группа из
попарно незнакомых между собой жителей.Доказательство. Допустим, что это не так и

- некоторая группа из

человек, а

- максимальная подгруппа из попарно незнакомых между собой жителей в ней, состоящая из

человек, где

. Условно выбросим из

любого жителя и получим некоторую группу

из

, где

, попарно незнакомых между собой человек. Если мы отбросим из

каждого человека из

вместе со всеми его знакомыми (которых по
лемме 1 не больше

), то в результате останется не менее

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

, получим

попарно незнакомых жителей - противоречие с максимальностью группы

.
Теперь, применив
лемму 2 c

и

, ко всему городу, получим некоторую группу

из

попарно незнакомых между собой жителей. Применив её ещё раз к оставшимся жителям,

и

, получим другую группу

из

попарно незнакомых между собой жителей. В группе, полученной объединением

и

, по условию найдётся тройка попарно знакомых жителей, из которых минимум двое будут из одной из групп

и

, что противоречит построению этих групп.
