TITLE: Proof about maximum amount of Spanning Trees in Complete Graph
QUESTION [2 upvotes]: How do I prove that the Complete Graph with $n$ ($n$ is even) vertices can have as much as $n / 2$ disjoint spanning trees (spanning trees that does not share an edge)?
So complete graph has $n(n-1)/2$ vertices and the spanning tree has $n - 1$. Then if we divide the first number by the second one we will get the answer, but I can't get why this is correct, because any $n-1$ edge may not form the spanning tree.

REPLY [1 votes]: Hint do it by induction. Adding a vertex adds a natural spanning tree - find it.
{"set_name": "stack_exchange", "score": 2, "question_id": 4122769}