Задача
COM-B2-M07-P004 Минимум рёбер для связности
#4
★★☆☆☆ Уровень 2 из 5
Докажите, что связный граф на \(n\) вершинах имеет не меньше \(n-1\) рёбер.
Удалите лишние рёбра до остовного дерева.
В любом связном графе есть остовное дерево. Остовное дерево содержит все \(n\) вершин и имеет ровно \(n-1\) рёбер. Исходный граф содержит все рёбра этого дерева и, возможно, ещё рёбра. Поэтому в нём не меньше \(n-1\) рёбер.
Задача связывает связность и деревья.