Prove that a graph cannot have two distinct spanning trees.

I'm confused with this proof. More so that I think I'm confused as what distinct in this context means? Initially I thought it was that these $2$ possible spanning trees cannot share the same edges, but in fact, distinct trees may still share some edges.

Any sort of clarification on this would help me a lot. Thanks

  • 4
    $\begingroup$ The result is simply false as stated: a graph can have many distinct spanning trees. Distinct simply means that no two of them are the same tree. (The result is true if the graph is itself a tree.) $\endgroup$ – Brian M. Scott Mar 19 '15 at 4:28
  • 7
    $\begingroup$ That is actually not true in general. Think of a simple example: the complete graph on $3$ vertices (a triangle). It has three distinct candidate spanning trees. Oh, and even if we interpret distinct as trees that do not share any edge, the claim is still not true: think of the complete graph on $4$ vertices. $\endgroup$ – megas Mar 19 '15 at 4:29
  • 1
    $\begingroup$ In fact, if the graph is connected, but is itself not a tree (equivalently, has a cycle), then it must have at least two distinct spanning trees (distinct in the sense of having at least one different edge). In other words, a graph has exactly one spanning tree if and only if it is itself a tree. $\endgroup$ – M. Vinay Mar 19 '15 at 15:36
  • $\begingroup$ Is this true if the proposition is changed to 'up to isomorphism'? $\endgroup$ – YoTengoUnLCD Dec 14 '15 at 3:54

Here's $K_4$ with two completely edge-disjoint spanning trees shown as red edges and green edges:

enter image description here

Here's $K_6$ with three edge-disjoint spanning trees:

enter image description here


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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