Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers

up vote 6 down vote accepted

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

            x---x---x  
            |   |   |  
            x---x---x
share|improve this answer
1  
Or of $K_4$, the complete graph on 4 vertices. –  Gerry Myerson Nov 14 '12 at 4:39
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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