# Transforming spanning trees through a sequence of intermediate trees

the problem is as follows: Let $G$ be a connected graph, and let $T_1$ and $T_2$ be two of its spanning trees. Prove that $T_1$ can be transformed into $T_2$ through a sequence of intermediate trees, each arising from the previous one and adding another.

I am confused whether this is a regular spanning tree problem which can be solved with Kruskal's greedy algorithm or if it is a question related to Huffman's algorithm. That is what I would like to know first, but the process of transforming one spanning tree into another through a sequence of intermediate trees is something that I am able to find a good example of online.

## 1 Answer

No, you don't need Kruskal's algorithm. Kruskal's algorithm deals with minimal spanning trees in a weighted graph, and your problem is about any spanning trees, not necessarily minimal (the graph isn't even weighted). I also don't see what this has to do with Hummfan's algorithm (if this is the one that you mean).

All you need to do is prove this lemma: given two distinct spanning trees $T_1$ and $T_2$ in graph $G$, it is possible to remove an edge from $T_1$ and add to it an edge from $T_2$ such that the resulting subgraph of $G$ is again a spanning tree.

Once you have this lemma, the statement from your question will follow by induction.

• I now see that it is truly a question related to the generation of trees within graph theory, which I know the theorems to now. Thanks for pointing me in the right direction! – AlPal Dec 4 '13 at 13:33