An undirected graph C has n nodes. Its adjacency matrix is given by an n × n…
2005
An undirected graph C has n nodes. Its adjacency matrix is given by an n × n square matrix whose (i) diagonal elements are 0's, and (ii) non-diagonal elements are l's. Which one of the following is TRUE?
- A.
Graph G has no minimum spanning tree (MST)
- B.
Graph G has a unique MST of cost n-1
- C.
Graph G has multiple distinct MSTs, each of cost n-1
- D.
Graph G has multiple spanning trees of different costs
Attempted by 163 students.
Show answer & explanation
Correct answer: C
Answer: The graph has multiple distinct minimum spanning trees, each of cost n-1.
Graph description: The adjacency matrix has 0 on the diagonal and 1 off-diagonal, so every pair of distinct nodes is connected by an edge of weight 1 (a complete graph with unit edge weights).
Cost of any spanning tree: Any spanning tree on n nodes has exactly n-1 edges, and each edge has weight 1, so the total cost of any spanning tree is (n-1)·1 = n-1.
Multiplicity of MSTs: Because all edges have equal weight, every spanning tree achieves the same cost n-1, so every spanning tree is a minimum spanning tree. Hence there are multiple distinct minimum spanning trees (for n ≥ 3).
Optional count note: The number of distinct labeled spanning trees on n nodes is n^(n-2) (Cayley’s formula), illustrating that there are many distinct MSTs when n>2.
Conclusion: Multiple distinct MSTs exist and each has cost n-1.