GATE CS 2005 Q6 — Minimum Spanning Trees

Based on the given adjacency matrix, the graph $G$ is a complete graph $K_n$ on $n$ vertices where:

• The diagonal elements are $0$, meaning there are no self-loops.
• All non-diagonal elements are $1$, meaning there is an edge of weight $1$ between every pair of distinct vertices.

Let's analyze the properties of the spanning trees of this graph:

1. Number of edges: Any spanning tree of a connected graph with $n$ vertices must contain exactly $n-1$ edges.
2. Cost of any spanning tree: Since every edge in $G$ has a weight of $1$, the cost of any spanning tree is: $$\text{Cost} = (n - 1) \times 1 = n - 1$$ Since all spanning trees have the same minimum possible cost, every spanning tree is a Minimum Spanning Tree (MST).
3. Number of distinct spanning trees: By Cayley's formula, the number of distinct spanning trees in a complete graph $K_n$ is $n^{n-2}$. For $n \ge 3$, this value is greater than $1$, meaning there are multiple distinct spanning trees.

Thus, the graph $G$ has multiple distinct MSTs, and each has a cost of $n-1$.