Register

Upper bound on the number of edge disjoint spanning trees in a complete graph of n vertices?

• retagged by
3,900 views

1 Answer

1 1 vote
Edge disjoint spanning trees are spanning trees that do not have any edges in common.

Kn has n(n-1)/2 edges ,and each spanning has n-1 edges so there are at most Floor[n/2] edges disjoint spanning tree.
Voting & Accepting an answer helps improve the community
← Previous · Of the following whi...Next → · Networking Book to f...
← Previous in category · Of the following whi...Next in category → · CMI2011-B-03
Position:
Show:

Related questions

0 0 votes
1 1 answer
1.4k
1.4k views
sonalrawat asked Aug 21, 2023
1,394 views
We are given a directed graph, represented as an adjacency list, in which each vertex has at least one incoming edge and one outgoing edge. We would like to print out for each vertex j the list of vertices pointing into j. What is the most accurate description of the complexity of computing these quantities in terms of n, the number of vertices, and m, the number of edges? O(n2) O(nm) O(m) O(n)
0 0 votes
3 3 answers
1.5k
1.5k views
Shankar Kakde asked Jan 24, 2019
1,544 views
Ace test series question on number of spanning trees possible
3 3 votes
3 answers 3 answers
9.6k
9.6k views
kapilbk1996 asked Feb 2, 2018
9,594 views
Ace Test Series: Graph Theory - Number Of Spanning Trees
How to approach such questions ? Please provide detailed solution. Answer given is option C
0 0 votes
1 1 answer
1.1k
1.1k views
angel rajput asked Feb 15, 2015
1,131 views
How to approach for calculating the number of paths of length n between 2 different vertices for a complete graph K4?
If I have any complete graph given then what is the approach to be followed up for calculating the number of paths of length n because for large value of n ,computation w...