Задача 31074

Темы:    [ Связность и разложение на связные компоненты ] [ Доказательство от противного ] [ Квадратные неравенства и системы неравенств ]

Сложность: 3+ Классы: 6,7,8

Условие

Из полного 100-вершинного графа выкинули 98 рёбер. Доказать, что он остался связным.

Решение

Предположим, что полученный граф оказался несвязным, и в одной из компонент связности n вершин. Тогда было выкинуто по крайней мере
n(100 – n)  рёбер, соединявших вершины этой компоненты с вершинами других компонент. Но  n(100 – n) = 50² – (n – 50)² ≥ 50² – 49² = 1·99 > 98.  Противоречие.

Источники и прецеденты использования

книга
Автор	Иванов С.В.
Название	Математический кружок
глава
Номер	5
Название	Графы
Тема	Теория графов
задача
Номер	06