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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
up vote 6 down vote accepted

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

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

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|cite|improve this answer

Your Answer


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.