edited by
1 flag 3,394 views
9 votes
9 votes
A complete graph G with 5 nodes has positive weight edges,each edge has a distinct weight with an integer value and maximum weight is equal to number of edges in G.

What can be maximum weight of minimum spanning tree for graph G?
  • ๐Ÿšฉ Duplicate | ๐Ÿ‘ฎ Hira Thakur | ๐Ÿ’ฌ โ€œhttps://gateoverflow.in/168648/minimum-spanning-treeโ€
edited by
1 flag

1 Answer

Best answer
6 votes
6 votes
Answer should be 14.
First take a complete graph with 4 vertices with edge weights (1,2,3,4,5,6) such that (1,2,3) and (4,5,6) forms a cycle. So that we can get maximum MST.
This maximum MST  has weight=1+2+4=7.
Now we still need to connect one vertex and we can do this by choosing the minimum of the remaining edges,i.e, edge with weight 7.
So total weight = 7+7=14.
selected by

Related questions

1 votes
1 votes
1 answer
1
radha gogia asked Feb 20, 2016
374 views
I tried by taking n=2 , and took points (1,1) ,(1,2) ,(2,2),(2,1) and I got the minimum weight to be 3 , which is n+1 but according to answer it is n-1
0 votes
0 votes
1 answer
2
vaishali bhatia asked May 23, 2017
459 views
For finding minimum number of spanning tree using kirchoff rule we construct adjacency matrix and find cofactors.so my question is what if we have 6*6 matrix or more than...
0 votes
0 votes
1 answer
3
atulcse asked Jan 13, 2022
476 views
How many minimum spanning trees are possible in this graph?
0 votes
0 votes
0 answers
4