Предположим, что полученный граф оказался несвязным, и в одной из компонент связности n вершин. Тогда было выкинуто по крайней мере

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

Ответ задачи отсутствует