How can I give a set of transitions sufficient to transform any spanning tree into any another spanning tree in a finite number of steps via spanning trees? I was wondering if someone help me.Thanks.



Spanning tree with sufficient transformation
I assume that by a transition you mean adding one edge and removing another. Then it seems that a simple algorithm works: Add an edge from the new tree. This will create a cycle so just remove one edge from the cycle that is not in the new tree. Such an edge must exist, since there are no cycles in the new tree. The running time is just the number of edges in the new cycle that are not in the original one.


