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

This question was previously asked in

GATE CS 2011 Official Paper

- 11
- 25
- 31
- 41

Option 3 : 31

The correct answer is **option 3.**

__Key Points__

For n=10, The graph is

Cost of the minimum spanning tree (MST) of a graph with n=10 nodes

The length of the path from ν5 to ν6 in the MST= 8+4+3+6+10 = 31

The path is V5⇒V6: (V5-V3-V1-V2-V4-V6)

India’s **#1 Learning** Platform

Start Complete Exam Preparation

Daily Live MasterClasses

Practice Question Bank

Mock Tests & Quizzes

Trusted by 2,29,15,288+ Students

Start your FREE coaching now >>

Testbook Edu Solutions Pvt. Ltd.

1st & 2nd Floor, Zion Building,

Plot No. 273, Sector 10, Kharghar,

Navi Mumbai - 410210

[email protected]
Plot No. 273, Sector 10, Kharghar,

Navi Mumbai - 410210

Toll Free:1800 833 0800

Office Hours: 10 AM to 7 PM (all 7 days)