No of spanning Trees

Question

Let $K_n$ denote the complete undirected graph with $n$ vertices where n is an even number. Find the maximum number of spanning trees of $K_n$ that can be formed in such a way that no two of these spanning trees have a common edge.

Comments

any method is there or only hit and try ?

Answer 1

This is not a solution. I want to ask in these spanning trees of K4. Which two spanning trees does not have a common edge??

Comments

k4 has only 2 spanning trees which do not have common edge .take suppose first from second row and second last from last row

---

thanx.....

---

The number of such spanning tree would ne n/2 which does not have common edge am I rite

---

Wrong..

Because such spanning trees will be in a pair. If you include one set then you cannot include another tree because then it will have edge in common.

For example, if you choose any one tree from row 2 then you can only have one tree from row 4 that will not have common edge. Hence its a pair. 

For unlabelled graph only possibility is maximum 2 trees that have complimentary edges and those trees will be the lines.  

Number of such pairable trees will be equal to number of ways we can label the n vertices of a graph. For K4 it is equal to n!/2 that is 4!/2 = 12. You can pick any one tree from row 2 , 3 and 4 and you'll definitely get its complimentary edged tree.

Answer 2

n/2

solution will be like this

(n-1)k=nC2

where k are no. of spanning trees having no common edge

Comments

How did you get (n-1)k=nC2  ?

Answer 3

Number of spanning tree will be:

$\frac{\binom{n}{2}}{n-1} =$ k

Here k is the number of spanning tree

Eg: for K4 answer will be 2...just check it

Now number of spanning tree will be 2.

          

Here you can clearly see, no edge is common.