Задача
COM-B1-M09-P009 Минимум ребер для связности
#9
★★☆☆☆ Уровень 2 из 5
Сколько минимум ребер может иметь связный граф на \(10\) вершинах?
Связный граф на \(n\) вершинах имеет хотя бы \(n-1\) ребер.
Минимум равен \(10-1=9\). Достигается, например, на пути из \(10\) вершин. Меньше быть не может, потому что для присоединения каждой новой вершины к уже построенной связной части нужно хотя бы одно ребро.
Важно дать и нижнюю оценку, и пример.