IAE Academy

GATE 2018 CS Q.47: solution and answer

GATE 2018 · CSQ.47 · 2 marks · NAT

Consider the following undirected graph G. Choose a value for x that will maximize the number of minimum weight spanning trees (MWSTs) of G. The number of MWSTs of G for this value of x is ______.

GATE 2018 CS question 47: An undirected weighted graph with 5 vertices arranged as: a top vertex (T), a left vertex (L), a right vertex (R), and two…Tap to open full size
Figure from the GATE 2018 CS paper. It is part of the question.
Figure description

An undirected weighted graph with 5 vertices arranged as: a top vertex (T), a left vertex (L), a right vertex (R), and two bottom vertices — bottom-left (A) and bottom-right (B). Edges: T–L weight 4; T–R weight x; T–A weight 1 (a diagonal from T down to A); T–B weight 3 (a diagonal from T down to B); L–A weight 4; A–B weight 4 (bottom edge connecting the two bottom vertices); B–R weight 5. Total 7 edges, 5 vertices.

Answer and solution

ANSWER

The value of x that maximizes the number of Minimum Weight Spanning Trees of G is x = 5, and the maximum number of MWSTs is 4.

Official answer: 4Source: Official answer key, GATE 2018 CS (IIT Guwahati)

  1. Label the five vertices T (top), L (left), R (right), A (bottom-left), B (bottom-right). The seven edges are T–A = 1, T–B = 3, T–L = 4, L–A = 4, A–B = 4, B–R = 5, and T–R = x.

  2. First build the MST on the sub-structure {T, L, A, B}, ignoring R and x, sorted by weight: T–A(1), T–B(3), then the tied trio T–L(4), L–A(4), A–B(4).

  3. Run Kruskal's greedy rule with tie-counting: T–A(1) is forced (unique minimum, no cycle) — merges {T,A}. T–B(3) is forced (unique next edge, no cycle) — merges {T,A,B}. Now only L remains unattached; among the weight-4 edges, A–B joins two vertices already in {T,A,B} so it would close a cycle and is excluded, leaving exactly two parallel ways to attach L: T–L or L–A. This gives 2 spanning trees on {T,L,A,B}, each of weight 1+3+4 = 8.

  4. Vertex R is incident to exactly two edges, T–R(x) and B–R(5), and both of R's endpoints (T and B) already lie inside the connected component {T,A,B} by the time weight 4 is processed (since 1 < 3 < 4), for any value of x that is not itself less than 4. So, as long as x is not used to disturb this ordering, attaching R is an independent step layered on top of the 2-way tie already counted for L.

  5. If x < 5, the unique cheapest edge into R is T–R(x), so R attaches in exactly 1 way, and the total MST count stays at 2 (only from the L-tie). Checking the boundary cases x=1, x=3, x=4 individually (where x ties with an existing edge weight and enters an earlier or the same weight-4 class) still yields exactly 2 MSTs in each case, because R never gets more than one viable cheapest edge in any of those scenarios.

  6. If x > 5, the unique cheapest edge into R is B–R(5), so again R attaches in exactly 1 way, and the count stays at 2.

  7. If x = 5, then T–R and B–R tie at weight 5, giving 2 independent parallel ways to attach R, exactly analogous to the L-tie. Since attaching R (via T or via B) never creates a cycle with either choice made for L, the two ties are independent and multiply: 2 (L-choices) × 2 (R-choices) = 4 distinct MSTs, each of total weight 1 + 3 + 4 + 5 = 13.

  8. Since R has only two incident edges (T–R, B–R) and L has only two incident edges (T–L, L–A), neither vertex can ever contribute more than a 2-way tie, so 2 × 2 = 4 is the maximum possible count over all choices of x — confirming x = 5 is optimal and the maximum number of MWSTs is 4.

KEY IDEA

When several edges tie for the same weight at the point a Kruskal-style MST construction needs to add a new vertex, each independent tie multiplies the MST count; here vertex L and vertex R each have exactly two incident edges, so the MST count can be at most 2×2=4, achieved only when both pairs tie simultaneously (which requires x=5, since L's tie is fixed at weight 4 and R's tie needs x to equal B–R's weight of 5).

WATCH OUT FOR

Treating only one of the two low-degree vertices (L or R) as capable of creating a tie and stopping after finding the L-tie gives 2 MSTs, missing that R independently ties at x=5 too, so the two 2-way ties multiply to 4 rather than just staying at 2; another common slip is forgetting that A–B, despite also being weight 4, cannot be used to attach L because both of its endpoints are already connected once T–A and T–B are chosen, so it must be excluded from the tie count.

From the GATE 2018 CS paper. Every question of this paper · Download the full paper · All 28 Graph algorithms questions, with notes

More Graph algorithms questions