We have a complete Graph G with |V|=n . We know it has n^(n-2) possible spanning trees. How many of them could be split into two equal halves by removing a single edge?

enter image description here


After some thought:

It's Choose(n n/2) * (((n/2)^(n/2 - 2))^2) * (n/2)^2

Pick the set of vertices that will remain on one side after splitting

Choose (n n/2)

How many spanning trees could exist on that group?

m = n/2, * = m^(m-2)

We have two sets :


Connect the two sets by two vertices each on each set:



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.