in Graph Theory
2,924 views
1 vote
1 vote
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.
in Graph Theory
by
2.9k views

1 comment

any method is there or only hit and try ?
0
0

Subscribe to GO Classes for GATE CSE 2022

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

4 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
0
0
thanx.....
1
1
The number of such spanning tree would ne n/2 which does not have common edge am I rite
0
0

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.

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

1 comment

How did you get (n-1)k=nC2  ?
0
0
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

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true