Задача
COM-B2-M07-P008 Связный граф с \(n-1\) рёбрами
#8
★★★☆☆ Уровень 3 из 5
Связный граф имеет \(n\) вершин и \(n-1\) рёбер. Докажите, что он является деревом.
Если есть цикл, можно удалить ребро цикла и сохранить связность.
Предположим, что в графе есть цикл. Удалим одно ребро этого цикла; связность сохранится. Тогда получим связный граф на \(n\) вершинах с \(n-2\) рёбрами.
Но связный граф на \(n\) вершинах имеет не меньше \(n-1\) рёбер. Противоречие. Значит, циклов нет, и граф является деревом.
Важно: здесь нужна связность.