GATE CS 2024 Set 2 | Question 59

NAT · 2 marks

The number of distinct minimum-weight spanning trees of the following graph is _________

Weighted undirected graph on seven vertices: g in the middle, b and c above it, f and e below it, a on the left and d on the right. Edge weights: a–b 1, a–f 1, c–d 1, d–e 1, b–c 3, f–e 3, and g is joined to each of a, b, c, d, e and f by an edge of weight 2.

Answer

9

Explanation

Think of Kruskal’s algorithm, which takes the cheapest edges first.

  • The four weight-1 edges \(ab, af, cd, de\) form no cycle, so every minimum spanning tree contains them. They leave three components: \(\{a, b, f\}\), \(\{c, d, e\}\) and \(\{g\}\).
  • Two more edges are needed, and all weight-2 edges meet \(g\): \(ga, gb, gf\) reach the first component and \(gc, gd, ge\) the second. A tree takes exactly one from each group, since two from the same group would close a cycle.
  • The weight-3 edges are never used.

So there are \(3 \times 3 = 9\) minimum spanning trees, each of weight 8.

Answer: 9