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. Graph Theory spanning-tree graph-theory + – dd asked Mar 19, 2017 dd 5.5k views answer comment Share Follow See 1 comment See all 1 1 comment reply sid1221 commented Jun 24, 2017 reply Follow Share any method is there or only hit and try ? 0 votes 0 votes Please log in or register to add a comment.
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?? akash.dinkar12 answered Mar 19, 2017 akash.dinkar12 comment Share Follow See all 4 Comments See all 4 4 Comments reply Akriti sood commented Mar 19, 2017 reply Follow Share 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 votes 0 votes akash.dinkar12 commented Mar 19, 2017 reply Follow Share thanx..... 1 votes 1 votes Kaluti commented Mar 26, 2017 reply Follow Share The number of such spanning tree would ne n/2 which does not have common edge am I rite 0 votes 0 votes APOORV PANSE commented Apr 7, 2017 reply Follow Share 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 votes 0 votes Please log in or register to add a comment.
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 nitish1995 answered Apr 11, 2017 nitish1995 comment Share Follow See 1 comment See all 1 1 comment reply Raju Kalagoni commented Dec 22, 2017 reply Follow Share How did you get (n-1)k=nC2 ? 0 votes 0 votes Please log in or register to add a comment.
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. samarpita answered May 13, 2022 samarpita comment Share Follow See all 0 reply Please log in or register to add a comment.