1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – AlPal Dec 4 '13 at 13:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.