Krdytkyu

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?

No, consider the complete graph $K_4$:

It has the following edge-disjoint spanning trees:

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:

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

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 $0leq 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.

Let me know with comments or editing what I messed up on the MathJax.

After observing the graphs presented by @Bjorn and @Gokul, I arrive at the conclusion that every complete graph $K_n$ with $ngeq4$ has at least two spanning trees with disjoint edges.

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 $ngeq4$ has wheel as its subgraph, so it directly follows that every complete complete graph with $ngeq4$ 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?