GATE CSE 2016 | Set 1 | Question: 39

Question

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 __________

Comments

In MST with distinct weights, 1st minimum weight and 2nd minimum weight must be selecetd according to Kruskal. But fo the 3rd min edge will only be selected if it does not create a cycle, else the 4th minimum weight edge is selected.

 Here, 4 vertices so we need 3 edges. edges of weight 1 and 2 must be selected. We can not choose weight 3 in case cycle is created in graph. select weight 4. so maximum weight for MST = 1+2+4=7.

---

This is a classic "Min-Max" problem that tests your understanding of the Greedy Property of Minimum Spanning Trees. 

 

---

 Solution for $n = 4$

 

A spanning tree for $n=4$ vertices must have exactly $|V| - 1 = 3$ edges. Kruskal’s algorithm picks edges in increasing order of weight, provided they don't form a cycle.

The Strategy: "The Wasteful Cycle"

To maximize the MST weight, we want to "waste" the smallest weights by putting them into a cycle as early as possible.

1. Form a Triangle ($K_3$): Take 3 vertices ($v_1, v_2, v_3$) and assign them the smallest weights: $1, 2,$ and $3$.

2. Kruskal's Execution:

   • Pick edge weight 1 (Connects $v_1, v_2$).

   • Pick edge weight 2 (Connects $v_2, v_3$).

   • Edge weight 3 now forms a cycle ($v_1-v_2-v_3-v_1$). Kruskal rejects weight 3.

3. Connect the Last Node: We still have one vertex left ($v_4$). It has 3 edges connecting it to the triangle. The remaining available weights are $\{4, 5, 6\}$. Kruskal’s is greedy, so it will pick the smallest available: weight 4.

4. Final MST: $\{1, 2, 4\}$.

5. Total Weight: $1 + 2 + 4 = \mathbf{7}$.

---

 Generalization for $n$ Vertices

The Proof

Let $G$ be a complete graph $K_n$. The total number of edges is $N = \frac{n(n-1)}{2}$. The weights are $\{1, 2, \dots, N\}$.

1. Isolate one vertex ($v_n$): Consider the subgraph $K_{n-1}$ formed by the other $n-1$ vertices.

2. Fill the Subgraph: The number of edges in $K_{n-1}$ is $M = \frac{(n-1)(n-2)}{2}$. Assign the weights $\{1, 2, \dots, M\}$ to these edges.

3. Spanning the Subgraph: Kruskal’s will process these $M$ edges first. To span $n-1$ vertices, it will pick the $n-2$ smallest edges: $1, 2, 3, \dots, (n-2)$. It will reject all other edges in this subgraph because they form cycles.

4. Connecting $v_n$: After processing the first $M$ edges, $v_n$ is still isolated. The edges connecting $v_n$ to the rest of the graph have weights starting from $M+1$ up to $N$.

5. The Final Edge: Kruskal’s will pick the smallest available edge to connect $v_n$, which is weight $M+1$.

Mathematical Derivation

The total weight $W$ of the MST is the sum of the $n-2$ edges used to span the first $n-1$ nodes, plus the single edge used to connect the $n$-th node:

$$W = \left( \sum_{i=1}^{n-2} i \right) + (M + 1)$$

Substitute $M = \frac{(n-1)(n-2)}{2}$:

$$W = \frac{(n-2)(n-1)}{2} + \left( \frac{(n-1)(n-2)}{2} + 1 \right)$$

$$W = (n-1)(n-2) + 1$$

$$W = n^2 - 3n + 3$$

---

 Verification

• For $n=4$: $4^2 - 3(4) + 3 = 16 - 12 + 3 = \mathbf{7}$.

---

We can make draw according to all different possibilities so how can we prove only 7 exactly

Answer 1

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.$

Comments

that graph will be mst but it will not have maximum weight in that case @ISHAN_KUMRA

---

yeah i got it cleared a long time ago 😅

---

Minimum possible weight = w1 + w2 + w3
Maximum possible weight = w1 + w2 + w4

applicable When Kruskal runs on that K4

Answer 2

Graph $G$ can be like this:

Comments

@Satbir

we can have edges 1 and 2, edge 3 makes cycle with 1-2, so take edge 4.
Now edge 5 makes cycle with 1-4 and similarly edge 6 makes cycle with 2-4, so now we can only take edge 7.

max MST weight= 1+2+4+7=14.

---

Is this not considered cycle ??

 

---

@Rohit0911 nope  if middle element were there then it will be CYCLE here it is not 

Answer 3

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

Comments

U should hav drawn the image of ur answer ...

---

explain why...dont only state

---

@puja.See this...

Answer 4

Corrections or suggestions are welcomed.

Comments

as in 2,3 (we need to select smaller one so 2 has been selected)

NOTE:-just take all possible maximum and out of all possible maximum pick minimum

---

@tanaya.... perfect one..thanks... finally it is clear

---

The best answer for this question

Answer 5

This question ask as how many possible way of drawing the above as to find MST in which maximum possible weight, so in which we can draw only in two ways. in first way MST is 1+2+3=6 and other 1+2+4=7 no other ways can draw. so max possible weight that MST is 7.

Answer 6

The question is asked such a way that you have make the weight maximum in a MST.No matter how you draw the graph you can't make the weight more that 7,It may be 6 or 7 but they asked about maximum possible weight that the MST have.So 7 is the maximum, You can' make it more than that because that will not be MST.

Comments

How can we prove that weight will not more than 7