0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.