5,515 views
1 votes
1 votes
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.

3 Answers

0 votes
0 votes

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??

0 votes
0 votes
n/2

solution will be like this

(n-1)k=nC2

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

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.

Related questions

7 votes
7 votes
1 answer
1
vishal chugh asked Jan 18, 2018
2,141 views
The number of distinct minimum spanning trees for the weighted graph shown below is ___________.
0 votes
0 votes
2 answers
3
Nidhi Budhraja asked Aug 31, 2018
735 views
Q1) Why is the path between a pair of vertices in a minimum Spanning tree of an undirected graph not the shortest( minimum weight) path?
1 votes
1 votes
1 answer
4
Amit puri asked Aug 22, 2016
3,006 views
Find the number of spanning trees in the following graph;