prove that every complete graph with 4 or more vertices has two spanning trees with disjoint edges

139 Views Asked by At

I read a possible proof of "every complete graph with 4 or more vertices has two spanning trees with disjoint edges" in the answer of another question.
That is, first claim that every complete graph with 4 or more vertices has a wheel as its subgraph, which I can understand.
Then claim that every wheel will have 2 spanning trees with disjointed edges because one is complement graph of another. I can find 2 spanning trees with disjointed edges in some specific wheels, but how to prove it generally?
Or is there other ways to prove the statement "every complete graph with 4 or more vertices has two spanning trees with disjoint edges"? Thanks.

1

There are 1 best solutions below

0
On BEST ANSWER

A wheel with $n$ vertices is a cycle $C_{n-1}$, joined to a single vertex $v$. Label the vertices of this cycle $u_1, u_2, \dots, u_{n-1}$.

Let the first spanning tree $T_1$ be the path $(v, u_1, u_{n-1}, u_{n-2}, \dots, u_2)$. Let the second spanning tree $T_2$ be the 'star' centered at $v$, with edges $vu_2, vu_3, \dots, vu_{n-1}$, as well as the single edge $u_1u_2$ of the cycle.

In the diagram below, $T_1$ is blue, and $T_2$ is red.

enter image description here