An undirected graph G (V, E) contains n (n > 2) nodes named ν_{1}, ν_{2}, ....ν_{n}. Two nodes ν_{i}, and ν_{j} are connected if and only if 0 < |i - j| ≤ 2. Each edge (ν_{i}, ν_{j}) is assigned a weight i + j.

The cost of the minimum spanning tree of such a graph with 10 nodes is :

This question was previously asked in

UGC NET Paper 3: Computer Science Nov 2017 Official Paper

Option 2 : 91

Official Paper 1: Held on 24 Sep 2020 Shift 1

16726

50 Questions
100 Marks
60 Mins

The correct answer is **option 2**

**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.

**EXPLANATION:**

- Two nodes νi, and νj are connected if and only if 0 < |i - j| ≤ 2
- Each edge (νi, νj) is assigned a weight i + j.

**Graph from the given conditions**

3 + 4 + 8 + 8 + 12 + 16 + 18 = 91

Therefore the minimum cost is 91