Граф на 300 вершинах обладает следующим свойством: если выбрать в нем любые 4 вершины, то по ребрам, соединяющим только эти вершины, можно из каждой вершины (из этих четырех) дойти в каждую (из этих четырех). Для какого наибольшего Х будет верно — задача №701616

Добавлена: 04.11.2026
Обновлена: 04.11.2026
Предмет: Геометрия
Автор: Кэмп

#Дискретная математика
#Теория графов

Условие:

Граф на 300 вершинах обладает следующим свойством: если выбрать в нем любые 4 вершины, то по ребрам, соединяющим только эти вершины, можно из каждой вершины (из этих четырех) дойти в каждую (из этих четырех). Для какого наибольшего Х будет верно утверждение: «В этом графе можно выбрать Х вершин так, что каждая из них соединена с каждой»?

Решение:

1. Дано

Количество вершин в графе $n = 300$ .
Свойство: любой подграф, порожденный любыми $4$ вершинами, является связным.

2. Найти

Наибольшее число $X$ такое, что в графе гарантированно существует клика размера $X$ (подграф, где каждая вершина соединена с каждой).

3. Решение

Шаг 1: Анализ условия связности Условие гласит, что для любых $4$ вершин подграф, ими порожденный, связен. Что это означает для структуры графа? Если бы в графе существовало независимое множество (множество вершин, где нет ни одного ребра) размером $4$ , то подграф, порожденный этими $4$ верши...