Предположим, что полученный граф оказался несвязным. Тогда его можно мысленно разделить на два подграфа, между которыми нет ребер (ни одна вершина первого подграфа не связана ни с какой вершиной второго подграфа). Обозначим количество вершин в первом подграфе за  Тогда было выкинуто по крайней мере  рёбер, соединявших вершины этого подграфа с вершинами другого подграфа. Но

Противоречие. Значит, свзяный граф получиться не мог.

Ответ: Нет