Complete graph has two edge disjoint spanning trees

Question

I read that a complete graph $K_n$ for $n \geq 4$ has (at least) two edge disjoint spanning trees. I know that the graph has to contain at least one spanning tree and I can show this for $n=4$. I hope that this result can be shown by induction, but honestly I don't really know how to do the induction. As I mentioned, the case $n=4$ can be shown be shown by an image, which I have done on paper. If it holds for an $n \geq 4$, however, I don't know how to show it for $n+1$. Thanks in advance for any help.

Answer 1

As you noted, the result for $n=4$ is easy; simply exhibit the required spanning trees. Now for $n>4$, take any spanning tree, $T$. Every tree has at least two leaves, so pick a leaf $L$. It is adjacent to exactly one edge, $e$, in $T$.

$K_{n}$$\setminus$$L$ is $K_{n-1}$ and $T$$\setminus$$e$ is a spanning tree for $K_{n}$$\setminus$$L$. By the induction hypothesis, $K_{n}$$\setminus$$L$ has at least one spanning tree, S, that is edge-disjoint from $T$$\setminus$$e$ in $K_{n}$$\setminus$$L$. Add any edge in $K_{n}$ other than $e$ that is adjacent to $L$ and join it to $S$. That is now an edge disjoint spanning tree for $K_{n}$.