4
$\begingroup$

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?

2 Answers 2

7

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

            x---x---x               |   |   |               x---x---x 
  • 2
    Or of $K_4$, the complete graph on 4 vertices.2012-11-14
1

This is actually false, even in the case of minimum spanning trees. In the case of Brian's example, you can even pick weighted edge values such that you can find two non-isomorphic minimum spanning trees.