I tried few cases and found any two spanning tree of a simple graph has some common edges. I mean I couldn't find any counter example so far. But I couldn't prove or disprove this either. How to prove or disprove this conjecture?

up vote 43 down vote accepted

No, consider the complete graph $K_4$:

It has the following edge-disjoint spanning trees: enter image description here

  • 2
    You can make each of the trees planar by taking one to be $N$-shaped and the other $Z$-shaped. You can make the whole thing planar by drawing the edge from the upper right vertex to the lower left vertex as a curve going outside the square. – Acccumulation Dec 5 at 20:29
  • @kelalaka We don't need a complete graph, no (imagine doing this same sort of thing on $K_5$ -- unless I've missed my guess, you have a few unused edges that can be removed, making it no longer complete (because each vertex needs 2-4 traversed edges connected to it, and each vertex in $K_5$ has 5 edges available, so each vertex is attached to at least one unused edge)). $K_4$ is probably just the best example -- it's well known, easy to visualize (comparatively few edges), and has very simple spanning trees. – Nic Hartley Dec 6 at 6:40

For the more interested readers, there are some research on decomposition of graph into edge-disjoint spanning trees.

For example, the classical papers On the Problem of Decomposing a Graph into $n$ Connected Factors by W. T. Tutte and Edge-disjoint spanning trees of finite graphs by C. St.J. A. Nash-Williams provides a characterization of graphs that contains $k$ pairwise edge-disjoint spanning trees.

For example, the paper Bi-cyclic decompositions of complete graphs into spanning trees by Dalibor Froncek shows how to decompose complete graphs $K_{4k+2}$ into isomorphic ${2k+1}$ spanning trees.

For example, the paper Factorizations of Complete Graphs into Spanning Trees with All Possible Maximum Degrees by Petr Kovář and Michael Kubesa shows how to factorize $K_{2n}$ to spanning trees with a given maximum degree.

You can search for more. For example, a Google search for decomposition of graph into spanning trees.

EDIT: This is incorrect as pointed out in the comments. As the other answer says, a spanning tree for $K_4$ can be done without sharing edges.

No, it's not true that any two spanning trees of a graph have common edges.

Consider the wheel graph:

enter image description here

You can make a spanning tree with edges "inside" the loop and another one from the outer loop.

  • 2
    but the outer loop doesn't reach the center node – amI Dec 5 at 6:21
  • You're right, I'll delete this answer as the other one suffices. – Gokul Dec 5 at 6:27
  • 10
    You can modify this by taking the out loop minus some "chord" plus some "radius" and its complement. – boboquack Dec 5 at 6:56
  • Yes. Actually I had seen that way only. @boboquack – Mr. Sigma. Dec 5 at 8:09

After observing the graphs presented by @Bjorn and @Gokul, I arrive at the conclusion that every complete graph $K_n$ with $n\geq4$ has at least two spanning trees with disjoint edges.
enter image description here

The graph given in the pic, which is wheel, has clearly two spanning trees with disjoint edges. In fact, every wheel will have exactly $2$ spanning trees with disjointed edges because one is complement graph of another.

Now, If we look at the solution of @Bjorn carefully, we find that his graph & spanning trees are homomorphic to the graphs shown in the pic. In fact, every complete graph $K_n$ with $n\geq4$ has wheel as its subgraph, so it directly follows that every complete complete graph with $n\geq4$ has at least 2 (or exactly $2$?) spanning trees with disjoint edges.

P.S: This observation gives birth to $2$ more interesting question.

  1. Is there any complete graph with more than $2$ spanning trees with disjoint edges? Or it will always have exactly $2$ spanning trees with disjoint edges.
  2. Is there any graph other than wheel or wheel as its subgraph having spanning trees with disjointed edges?
  • These questions and beyond have been answered in the papers I cited. If you are interested, you can take a look. – Apass.Jack Dec 6 at 5:33
  • Thanks @Apass.Jack I have seen your answer. Will look at it. – Mr. Sigma. Dec 6 at 5:35

For $K_{2k}$, I believe that

$$G_1 = \{ (v_{2i},v_{2i+1} ),(v_{2i},v_{2i+2}),\dots,(v_{2k-2},v_{2k-1})\},$$

$$G_2 = \{ (v_{2i+1},v_{2i+2}),(v_{2i},v_{2i}),\dots(v_{2(k-1)},v_{2(k-1)})\}$$

for $0\leq i < k$ are counterexamples. That is, for the first graph, take the vertices with even indices and connect them to the next vertex, and for all but the last even vertex, connect it to the vertex after that as well. For the second graph, do this with odd vertices.

And inductively, once we have a counterexample for $n$ vertices, it's easy to construct a counterexample with $n+1$ vertices by connecting the new vertex with one edge for one graph, and with another edge for the other.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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