Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry W_{ij} in the matrix W below is the weight of the edge {i, j}

\(W = \begin{pmatrix} 0 & 1 & 8 & 1 & 4 \\\ 1 & 0 & 12 & 4 & 9 \\\ 8 & 12 & 0 & 7 & 3 \\\ 1 & 4 & 7 & 0 & 2 \\\ 4 & 9 & 3 & 2 & 0 \end{pmatrix}\)

This question was previously asked in

GATE CS 2010 Official Paper

Option 4 : 10

The correct answer is **option 4**

__Concept:__

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges(V – 1 ) of a connected, edge-weighted undirected graph G(V, E) that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

__Graph from the Adjacency matrix:__

\(W = \begin{pmatrix} 0 & 1 & 8 & 1 & 4 \\\ 1 & 0 & 12 & 4 & 9 \\\ 8 & 12 & 0 & 7 & 3 \\\ 1 & 4 & 7 & 0 & 2 \\\ 4 & 9 & 3 & 2 & 0 \end{pmatrix}\)

Minimum possible weight of a spanning tree taking the vertex 0 as a leaf node:

Sum of the weight of this MST = 1 + 4 + 2 + 3 = 10

So,10 is the minimum possible weight of a spanning tree when taking vertex 0 as a leaf node