A company consists of persons, and each of them can sit at a round table so that each two neighbors would be familiar to each other. Prove that all persons can sit at a round table with the same property to be satisfied. (S. Volchenkov)
В компании из семи человек любые шесть могут сесть за круглый стол так, что каждые два соседа окажутся знакомыми. Докажите, что и всю компанию можно усадить за круглый стол так, что каждые два соседа окажутся знакомыми. (С. Волчёнков)
Заметим, что у каждого в компании не менее трёх знакомых.
Действительно, если бы некто был знаком менее, чем с тремя, то, исключив из компании одного из его знакомых, мы получили бы шестёрку людей, в которой у не более одного знакомого, т. е. посадить их за круглый стол невозможно. Более того, если бы у каждого было ровно по три знакомых, то число пар знакомых людей было бы равно , что невозможно.
Значит, у какого-то человека хотя бы знакомых. Рассадим всех, кроме , за круглый стол. Тогда из четырёх его знакомых хотя бы двое сидят рядом. Если мы посадим между ними, то получим требуемую рассадку.