Предположим, что это не так, тогда какие то две вершины не соединены. Будем так же отбрасывать "одиночные" вершины. Тогда по нашему предположению должно остаться 2 или больше не связанных вершины в конечном графе, где нет ребер. Чего быть не может, т.к. иначе кол-во ребер и вершин отличались на 2 или более, а не на 1.
