Задача
COM-B1-M09-P014 Ребер не меньше вершин
#14
★★★☆☆ Уровень 3 из 5
Докажите, что если граф на \(n\) вершинах имеет не меньше \(n\) ребер, то в нем есть цикл.
Граф без циклов - лес.
Если в графе нет циклов, то каждая его компонента является деревом. Если компоненты имеют размеры \(n_1,\ldots,n_k\), то ребер в них \((n_1-1)+\cdots+(n_k-1)=n-k\le n-1\). Значит граф без циклов имеет не более \(n-1\) ребер. Если ребер хотя бы \(n\), цикл обязателен.
Первый серьезный аргумент через лес.