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.


1 Answer 1


Hint do it by induction. Adding a vertex adds a natural spanning tree - find it.

  • $\begingroup$ @AlexJackson : If you only need a predicate, $P$, to be true on even numbers, then use $P(n-2)$ to prove $P(n)$. $\endgroup$ Commented May 1, 2021 at 0:24
  • $\begingroup$ Yep, I got it and then deleted my comment. $\endgroup$ Commented May 1, 2021 at 0:26
  • $\begingroup$ Can you finish it? I could not do it with even reading the blog linked above. $\endgroup$ Commented May 1, 2021 at 0:35
  • $\begingroup$ @AlexJackson No, sorry, my union is opposed to my doing your homework. $\endgroup$
    – Igor Rivin
    Commented May 1, 2021 at 2:20
  • $\begingroup$ By "adding a vertex" did you mean "adding two vertices"? $\endgroup$
    – bof
    Commented May 1, 2021 at 2:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .