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

Добавлена: 17.09.2026
Обновлена: 17.09.2026
Предмет: Логика
Автор: Кэмп

#Теория доказательств
#Математическая логика

Условие:

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

Решение:

Дано:

Множество зверей $V$ , где $|V| = 7$ .
Отношение «быть друзьями» задает граф $G = (V, E)$ , где вершины — это звери, а ребра — наличие дружбы между ними.
Условие: для любого подмножества $S \subset V$ , такого что $|S| = 6$ , существует гамильтонов цикл в подграфе $G[S]$ , индуцированном этими вершинами.

Найти:

Доказать, что в исходном графе $G$ существует гамильтонов цикл (то есть всех семерых можно рассадить так, чтобы каждый соседствовал с друзьями).

Решение:

Шаг 1: Анализ условия. Обозначим зверей как вершины графа $V = \{v_1, v_2, v_3, v_4, v_5, v_6, v_7\}$ . Условие гласит, что если мы удалим любую вершину $v_i$ ...