TITLE: Prove that even $n$ can be partitioned to $\frac n2$ edges
QUESTION [1 upvotes]: I have to show that the edges of a complete graph on $n$ vertices for even $n$ can be partitioned into $\frac n2$ edge disjoint spanning trees. 
I know that a complete graph has $\frac{n(n-1)}{2}$ edges. And for reference, a spanning tree is a tree on all $n$ vertices, so it has $n-1$ edges. But I don't know how to show my statement.

REPLY [1 votes]: Hint: induction.


 Suppose it is possible for $K_{2n}$, we prove it is possible for the complete graph on $\{1,2,\dots ,2n+2\}$. Let $T_1,T_2\dots T_n$ be spanning subtrees that partition the complete graph on $\{1,2,3\dots 2n\}$. Let $G_i$ be the spanning tree on $\{1,2,\dots ,2n+2\}$ defined by $T_i\cup(2n+1,i)\cup(2n+2,i+n)$. It should be clear the spanning trees $G_1,G_2\dots G_n$ contain all of the edges of the $K_{2n+2}$ exactly once, except for edge $(u,v)$ and the edges $(i,2n+2)$ and $(n+i,2n+1)$, with $1\leq i\leq n$ (which are contained zero times). Luckily these "extra" edges form a spanning tree on $\{1,2\dots 2n+2\}$. So we are done.
{"set_name": "stack_exchange", "score": 1, "question_id": 1651363}