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?
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.Sign up to join this community
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: