[Math] Spanning trees implies isomorphism

graph theory

I'm having trouble solving this question:

Prove or disprove the following statement: Given a graph G, if T and U are spanning trees
of G, then T and U are isomorphic.

I know that two graphs are isomorphic if they have an "edge-preserving bijection." I also know that a spanning tree of a graph G is a connected graph that can be defined as a maximal set of edges of G that contains no cycle.

How would I go about proving or disproving?

Best Answer

BIG HINT: Find non-isomorphic spanning trees of this graph:

            x---x---x  
            |   |   |  
            x---x---x
Related Question