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?


7 Answers 7


No, consider the complete graph $K_4$:

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

  • 2
    $\begingroup$ 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. $\endgroup$ Commented Dec 5, 2018 at 20:29
  • $\begingroup$ @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. $\endgroup$
    – anon
    Commented Dec 6, 2018 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.

  • 3
    $\begingroup$ but the outer loop doesn't reach the center node $\endgroup$
    – amI
    Commented Dec 5, 2018 at 6:21
  • $\begingroup$ You're right, I'll delete this answer as the other one suffices. $\endgroup$
    – Gokul
    Commented Dec 5, 2018 at 6:27
  • 10
    $\begingroup$ You can modify this by taking the out loop minus some "chord" plus some "radius" and its complement. $\endgroup$
    – boboquack
    Commented Dec 5, 2018 at 6:56
  • $\begingroup$ Yes. Actually I had seen that way only. @boboquack $\endgroup$
    – Mr. Sigma.
    Commented Dec 5, 2018 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?
  • $\begingroup$ These questions and beyond have been answered in the papers I cited. If you are interested, you can take a look. $\endgroup$
    – John L.
    Commented Dec 6, 2018 at 5:33
  • $\begingroup$ Thanks @Apass.Jack I have seen your answer. Will look at it. $\endgroup$
    – Mr. Sigma.
    Commented Dec 6, 2018 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.


We can show that any complete graph of size $n > 3$ has two edge-disjoint linear trees. Choose $1 < k < n-1$ relatively prime to $n$; this is always possible when $n > 3$. One spanning tree is obtained by the edges $$ E_1 = \{ \{i, i+1\}: 0 \leq i < n-1\} $$ where we identify the vertices with $\{0, \ldots, n-1\}$. For the second tree define $j_0 = 0$ and $$ j_{i+1} \equiv j_i + k\ \mathrm{mod}\ n $$ and set $$ E_2 = \{\{j_i, j_{i+1}\}: 0 \leq i < n-1\}. $$ This defines a spanning tree because $k$ is an additive generator of $\mathbf{Z}/n\mathbf{Z}$.

Suppose $e \in E_1 \cap E_2$ and $e = \{i, i+1\}$. This means that either $$ i+1 \equiv i+k\ \mathrm{mod}\ n \implies k \equiv 1\ \mathrm{mod}\ n $$ or that $$ i \equiv i+1+k\ \mathrm{mod}\ n \implies k \equiv -1\ \mathrm{mod}\ n. $$ The first is impossible because $k > 1$, and the second is impossible because $k < n-1$.


If the graph has a bridge (i.e. an edge whose removal disconnects the graph), then this edge must belong to every spanning tree. Intuitively, a bridge is the only edge connecting its two endpoints and so necessarily belongs to every connected subgraph.

On the other hand, if an edge of the graph belongs to a cycle, then there exists a spanning tree not containing this edge.

So, if every edge of a graph belongs to a cycle, then no edge is common to all spanning trees (i.e., the intersection of the edge sets of the spanning trees is the empty set).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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