edited by
35,080 views
85 votes
85 votes
Let $G$ be a complete undirected graph on $4$ vertices, having $6$ edges with weights being $1, 2, 3,  4, 5,$ and $6$. The maximum possible weight that a minimum weight spanning tree of $G$ can have is __________
edited by

18 Answers

Best answer
144 votes
144 votes
Many people here have not understood the question itself. Consider a complete graph of $4$ vertices. We have a total of $6$ edges of given weights but we do not have the exact graph. Many different graphs are possible each having a different structure. Consider these $2$ graphs, both of them are different. We do not know the exact structure of the graph, so what the question wants is to find the MST of all such structures and out of these tell the weight of the MST having maximum weight. The point about the MST of a graph with unique edge weights is valid for a given structure of the graph. With the same set of edge weights more than $1$ graph is possible and all of them can have different MSTs.

My solution: Draw a complete graph of $4$ vertices. Sort given edges $y$ weight in increasing order. Just like Kruskal's algorithm sort the edges by weight. MST of graph with $4$ vertices and $6$ edges will have $3$ edges. Now in any case we will have to include edges with weights $1$ and $2$ as they are minimum and Kruskal's algorithm includes minimum weight edge if it does not form a cycle. We can not have a cycle with $2$ edges. In Kruskals algorithm, an edge will be rejected if it forms a cycle with the edges already selected. To increase the weight of our MST we will try to reject the edge with weight $3.$ This can be done by forming a cycle. The graph in pic1 shows this case. This implies, the total weight of this graph will be $1+2+4 = 7.$
edited by
79 votes
79 votes

Graph $G$ can be like this:

edited by
30 votes
30 votes
ans is 7.

it is said maximum weight pssbl.

draw a triangle. 3 sides weight 1 2 3. and 4th point is in center. join it with tringle vertices.. got more 3 sides. new side weight 4 5 6. now draw mst. take 1 take 2. cant take 3, so take 4. 1+2+4=7
edited by
18 votes
18 votes

Corrections or suggestions are welcomed.

Answer:

Related questions

61 votes
61 votes
5 answers
3
Sandeep Singh asked Feb 12, 2016
28,244 views
Consider the following directed graph:The number of different topological orderings of the vertices of the graph is _____________.