Question

Докажите, что если граф не содержит циклов и имеет n вершин и n-1 ребро, то он связен.

Answer 1

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