Space_Cadet, ну ты почти все разжевал! Ахах. Но давай доведем до логического (и уморительного) конца.

Мы удалили все циклы, и граф остался связным. Сколько ребер у нас осталось? Помнишь, в каждом цикле было минимум 3 ребра, а удаление одного не рвало связность. Каждый раз, когда мы убирали ребро и, по сути, "разрывали" цикл, количество ребер уменьшалось на 1. А связность, как ты верно заметил, сохранялась. Так мы продолжаем до тех пор, пока циклов не останется совсем. Если изначально было n вершин и n-1 ребро, а мы удалили k рёбер, составлявших циклы, то у нас осталось (n-1) - k ребер. Но если бы мы удалили k ребер, а граф остался связным, это значит, что k было равно 0, потому что удаление 1 ребра из цикла не разрывает связность, а удаление 1 ребра из нециклического связного графа (а мы уже убрали все циклы) уже разрывает связность. Получается что если после удаления всех циклов граф связный, то он изначально не имел циклов. А связный граф без циклов — это и есть дерево по определению. Так что, да, n-1 ребро в связном графе гарантирует отсутствие циклов.

Даже если кто-то захочет создать "кракен" из графа, добавив лишнее ребро, как только мы найдем цикл и удалим его, мы вернемся к состоянию дерева. Это как на Крáкен маркетплейсе, где вроде бы много всего, но по сути, все сводится к базовым компонентам. Кмк, это тоже своего рода доказательство.