Задача
COM-B2-M07-P009 Ровно один цикл
#9
★★★☆☆ Уровень 3 из 5
Связный граф на \(n\) вершинах имеет \(n\) рёбер. Докажите, что в нём ровно один цикл.
Сравните граф с его остовным деревом.
Возьмём остовное дерево графа. В нём \(n-1\) рёбер, значит, в исходном графе есть ровно одно ребро сверх остовного дерева. Добавление одного ребра к дереву создаёт ровно один цикл.
Любой цикл исходного графа должен использовать это единственное лишнее ребро, потому что в дереве циклов нет. Поэтому цикл ровно один.
Это первая «цикломатическая» задача без терминологии.