графы - Как доказать наличие циклов в графе?

Рассмотрим в каждой из связных компонент графа максимальное поддерево $%T_i$%, а также отметим одну из вершин $%o_i$%. Если $%n_i$% -- число вершин этой связной компоненты, то в дерево входит в точности $%n_i-1$% ребро. Общее количество рёбер, входящих в деревья, равно $%\sum (n_i-1)\le n-1$%, где $%n=\sum n_i$% -- общее число вершин. По условию, общее количество рёбер равно $%2n$%, поэтому имеется по крайней мере $%n+1$% ребро, не входящее ни в одно из деревьев.

Пусть $%e$% -- одно из таких рёбер с началом $%u$% и концом $%v$%, принадлежащее $%i$%-й связной компоненте. Рассмотрим следующий цикл с началом и концом $%o_i$%. Сначала пройдём по рёбрам выбранного поддерева кратчайшим путём из $%o_i$% в $%u$%, затем пройдём ребро $%e$%, и далее вернёмся в $%o_i$% по кратчайшему пути в поддереве $%T_i$% из $%v$% в $%o_i$%. Рассмотренный цикл $%\gamma(o_i,u)e\gamma(v,o_i)$%, вообще говоря, не является простым. Здесь $%\gamma$% обозначает кратчайший (геодезический) путь из одной вершины в другую по рёбрам поддерева. Если мы теперь рассмотрим максимальное общее начало $%p$% путей $%\gamma(o_i,u)$% и $%\gamma(o_i,v)$%, то рассмотренный нами путь примет вид $%pqp^{-1}$%, где $%q$% является простым циклом. Длина такого цикла не меньше $%1$% и не больше $%n$%, а самих таких циклов мы построили столько, сколько имеется рёбер, не входящих в поддеревья вида $%T_i$%. Все они попарно различны, так как каждый цикл содержит ровно одно ребро не из поддеревьев. Поскольку циклов построено не меньше $%n+1$%, по принципу Дирихле какие-то два из них должны иметь одинаковую длину.

Добавление. Небольшое упрощение по ходу дела. Можно не отмечать точки в компонентах связности, а для каждого ребра $%e$%, не входящего в дерево, брать кратчайший путь $%s$% в этом дереве от конца $%e$% к началу $%e$%. Тогда сразу возникает простой цикл $%es$%, свой для каждого такого ребра $%e$%.