GATE Overflow Test Series | Mock GATE | Test 4 | Question: 47

Question

An undirected graph $G(V,E)$ contains $n(n>2)$ nodes named as $1,2,3,4, \dots , n$. Two vertices are adjacent if $0 < \mid i-j \mid \leq 2.$ All the edge weights is unity. How many MST are possible for $n=4$?

Comments

apply kirchoff’s condition, and find the cofactor of any element in the matrix, you will get 8

Answer 1

To connect 4 vertices we need 3 edges,

In total, we have 5 edges, so $5\choose3$ = $10$

Now in this, we have counted the MST where there will be a cycle formed with the vertices

1 – 2 – 3 connected and 4 disconnected

2 – 3 – 4 connected and 1 disconnected

So, we remove these cases from total of 10

Ans = 10 - 2 = 8

Answer 2

Total number of edges in the graph when $n=4$ are $5$, for MST we must select $3$ edges. so total possible ways will be $^5C_3 = 10$. But out of these selections in $2$ of the cases the graph gets disconnected.


















MST neither create cycle nor disconnected graph.

So the number of MST are $10-2 = 8$.