Утверждение о том, что в любом связном графе существует остовное дерево, доказывается с помощью удаления из графа избыточных рёбер. 34

Процесс происходит так: 3

1. Начинают с исходного связного графа, который можно представить как структуру со множеством узлов и циклов. 3
2. Пока в графе есть циклы, удаляют по одному ребру из каждого из них. 3 Это сохраняет связность, но устраняет замкнутость. 3
3. В результате получают граф без циклов, который остаётся связным, — это и есть остовное дерево. 3

Таким образом, остовное дерево получается, если из исходного графа удалить максимальное число рёбер, входящих в циклы, но при этом не нарушать связность графа. 12