Задача
COM-B1-M09-P015 Связный граф с \(n-1\) ребрами
#15
★★★☆☆ Уровень 3 из 5
Докажите, что связный граф на \(n\) вершинах и \(n-1\) ребрах не имеет циклов.
Если есть цикл, можно удалить одно ребро цикла и связность сохранится.
Предположим, что цикл есть. Удалим одно ребро этого цикла. Между его концами все равно остается путь по остальной части цикла, поэтому граф остается связным. Тогда получится связный граф на \(n\) вершинах с \(n-2\) ребрами, что невозможно, так как связный граф имеет не меньше \(n-1\) ребер. Значит циклов нет.
Это одно из определений дерева в действии.