Решение задачи 432

Условие:

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

Решение:

Интерпретируем на языке графов: вершины — люди, ребра — знакомства. Степень каждой вершины хотя бы 2, потому что у каждого человека (когда он за столом) соседи справа и слева его друзья. Покажем, что степень каждой вершины хотя бы 3. Пусть у вершины А степень равна двум, то есть А соединена с В и С. Уберем вершину В из графа (и все ребра, выходящие из нее), тогда в оставшемся графе есть цикл, проходящий по всем вершинам, но у вершины А степень стала 1, противоречие.

Как известно, в любом графе сумма степеней всех вершин четна, значит найдется человек Х, у которого хотя бы 4 друга. Всех, кроме него, рассадим по кругу так, чтобы сидящие рядом были знакомы. У человека Х хотя бы 4 друга, значит среди них найдутся двое, сидящие рядом. Посадим Х между ними.