retagged by
808 views
0 votes
0 votes
Suppose that average edge weight for a graph G is Aavg. Then the minimum spanning tree of G will have weight at most

(n-1) Aavg. Where n is number of vertices in graph G.

i think think is false but in  a solution mannul it is given as true please check it.
retagged by

1 Answer

5 votes
5 votes

See in the given graph below.  The average weight is 2+2+2+10 /4 =4. And the minimum spanning tree weight is  AD +AC +AB= 14. 

Clearly this is not less than n-1 *avg which is 3*4=12.

Thus the above case would fail in case there is a bridge vertex with maximum weight. 

edited by

Related questions

0 votes
0 votes
1 answer
1
Lakshman Bhaiya asked Nov 8, 2018
1,031 views
How many numbers of spanning tree are possible?
0 votes
0 votes
2 answers
2
iarnav asked Apr 28, 2018
383 views
Let G be a connected simple graph with non distinct edge weights. Now, e be the lightest edge in G. So, does this edge e is present in every MST of G?My take - when all e...