Задача
COM-B2-M07-P006 Рёбра в лесу
#6
★★★☆☆ Уровень 3 из 5
Лес имеет \(n\) вершин и \(c\) компонент связности. Докажите, что в нём \(n-c\) рёбер.
Каждая компонента леса является деревом.
Пусть компоненты имеют \(n_1,n_2,\ldots,n_c\) вершин. Каждая компонента — дерево, поэтому в ней \(n_i-1\) рёбер. Всего рёбер
\[\sum_{i=1}^c(n_i-1)=\sum_{i=1}^c n_i-c=n-c.\]
Часто используется как подсчёт компонент через рёбра.