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?

$\endgroup$
0

4 Answers 4

7
$\begingroup$

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

            x---x---x  
            |   |   |  
            x---x---x
$\endgroup$
1
  • 2
    $\begingroup$ Or of $K_4$, the complete graph on 4 vertices. $\endgroup$ Commented Nov 14, 2012 at 4:39
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

Actually, graph which possesses this property would be quite a rare thing. Still, there are some connected graphs which are not trees but any two spanning trees in them are isomorphic. An easy example---any cyclic graph. Another one---take a triangular graph $ABC$ (complete graph with three vertices) and an arbitrary tree $T$ with root $r$. Then "glue" $T$ to each of the vertices of $ABC$ by identifying $r$ and $A$, $r$ and $B$, $r$ and $C$ respectively, so you get graph $G$ which has rotational symmetry (it maps into itself when "rotated" by $120$ degrees). Obviously, $G$ has three spanning trees---namely, $G \backslash AB$, $G \backslash BC$, and $G \backslash CA$, and they are all isomorphic to each other. This can be generalized to taking a cyclic graph with $n$ vertices and gluing $n$ copies of $T$ to its vertices.

Here is another question, though---does there exist a graph (not a multigraph, mind you, but a regular graph, so double edges and loops are not allowed) with more than one simple cycle which possesses this property? I haven't really thought too long about it---but it could have a nice elementary solution...

$\endgroup$
0
$\begingroup$

Find two nonisomorphic trees with the same number of vertices. Draw them on the same vertex set. Their union is a graph with two nonisomorphic spanning trees.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .