Graph Fundamentals, Trees and Connectivity Practice Questions for GATE CS

Solve 127+ Graph Fundamentals, Trees and Connectivity practice questions for GATE CS with answers and detailed solutions. Free sample questions below.

Chapter Roadmap: Graph Fundamentals, Trees and Connectivity

Chapter Journey

Graph Fundamentals & Connectivity

1. Spanning Tree Enumeration

Counting trees using Cayley’s Formula & Kirchhoff’s Theorem.

2. Weighted Spanning Trees

Optimizing tree weight with Kruskal’s & Prim’s Algorithms.

3. Connectivity & Planarity

Graph robustness, Euler’s Formula, and edge bounds.

4. Matchings & Distances

Pairing vertices, diameter, and graph powers.

Why start here? Counting structures builds the intuition needed to optimize them and analyze their resilience.

Hero Concept: What is a Spanning Tree?

The Spanning Tree

For a connected undirected graph $G = (V, E)$ with $∣ V ∣ = n$ , a Spanning Tree $T$ is a subgraph that:

1. Includes all vertices:

V (T) = V (G)

2. Is connected

3. Is acyclic (No loops)

Critical Property

∣ E_{T} ∣ = n - 1

Why Enumerate? Knowing the number of spanning trees, denoted as $τ (G)$ , tells us how many unique ways we can connect all nodes without loops.

Graph Fundamentals, Trees and Connectivity: Solved Questions with Step-by-Step Explanations (10 Problems)

Question 1 · Engineering Mathematics MCQ

Consider a connected simple graph with 10 vertices. If we partition its edges into a spanning tree and a set of extra edges, and the total number of edges is 15, how many edges are in the extra set?

A.
6
B.
5
C.
4
D.
9

Correct Answer:

Step-by-Step Solution

Insight: A spanning tree of an $n$ -vertex graph always contains exactly $n - 1$ edges.

Exam route: The spanning tree has $10 - 1 = 9$ edges. The extra edges are the total minus the tree edges: $15 - 9 = 6$ .

Learning route:

Identify the total number of vertices $n = 10$ and total edges $E = 15$ .
Recall that any spanning tree of a graph with $n$ vertices must have exactly $n - 1$ edges.
Calculate the number of edges in the spanning tree: $10 - 1 = 9$ .
The extra edges are those not in the spanning tree. Subtract the tree edges from the total: $15 - 9 = 6$ .

Answer: 6

Question 2 · Engineering Mathematics MCQ

Assertion (A): For a graph with 6 vertices, the reduced Laplacian matrix used in Kirchhoff's theorem is of size $5 \times 5$ .

Reason (R): The original Laplacian matrix is of size $6 \times 6$ , and the method requires deleting exactly one row and one column.

A.
Both A and R are true and R is the correct explanation of A
B.
Both A and R are true but R is NOT the correct explanation of A
C.
A is true but R is false
D.
A is false but R is true

Correct Answer:

Step-by-Step Solution

Insight: Kirchhoff's theorem requires reducing the $n \times n$ Laplacian to an $(n - 1) \times (n - 1)$ matrix by deleting one row and one column.

Exam route: For $n = 6$ , the original matrix is $6 \times 6$ . Deleting one row and one column yields a $5 \times 5$ matrix. R correctly explains why A is true.

Learning route:

Recall the statement of Kirchhoff's Matrix Tree Theorem.
The theorem states that the number of spanning trees is the determinant of any cofactor of the Laplacian matrix $L$ .
A cofactor is obtained by deleting exactly one row $i$ and one column $j$ (usually $i = j = 1$ ).
For a graph with $n = 6$ vertices, $L$ is a $6 \times 6$ matrix.
Deleting one row and one column reduces the dimensions by 1, resulting in a $5 \times 5$ matrix.
Thus, both A and R are true, and R is the direct mathematical reason for A.

Answer: Both A and R are true and R is the correct explanation of A

Question 3 · Engineering Mathematics MCQ

Consider the following:

Assertion (A): A connected planar graph with 10 vertices and 15 edges has 7 faces.

Reason (R): Euler's formula for connected planar graphs states $V - E + F = 2$ .

A.
Both A and R are true, and R is the correct explanation of A
B.
Both A and R are true, but R is NOT the correct explanation of A
C.
A is true but R is false
D.
A is false but R is true

Correct Answer:

Step-by-Step Solution

Key idea: Use Euler's formula to verify the assertion.

Step 1: Euler's formula states $V - E + F = 2$ for connected planar graphs. So Reason (R) is true.

Step 2: Given $V = 10$ , $E = 15$ , substitute into Euler's formula: $10 - 15 + F = 2$ .

Step 3: Solve for $F$ : $F = 2 - 10 + 15 = 7$ .

Step 4: The assertion states $F = 7$ , which matches our calculation. So Assertion (A) is true.

Step 5: Reason (R) correctly explains why Assertion (A) is true.

Answer: Both A and R are true, and R is the correct explanation of A.

Question 4 · Engineering Mathematics MCQ

The number of spanning trees in a complete graph with 5 labeled vertices is

A.
125
B.
625
C.
24
D.
120

Correct Answer:

Step-by-Step Solution

Insight: Direct application of Cayley's formula for complete graphs.

Exam route: The formula for the number of spanning trees in $K_{n}$ is $n^{n - 2}$ . For $n = 5$ , this is $5^{5 - 2} = 5^{3} = 125$ .

Learning route:

Identify the graph as a complete graph $K_{n}$ with labeled vertices.
Recall Cayley's formula: $τ (K_{n}) = n^{n - 2}$ .
Substitute $n = 5$ into the formula: $5^{5 - 2} = 5^{3}$ .
Calculate $5^{3} = 125$ .

Answer: 125

Question 5 · Engineering Mathematics MCQ

Which of the following statements about the row sums of the Laplacian matrix $L$ of a simple undirected graph is true?

A.
The sum of elements in any row is always 0
B.
The sum of elements in any row is equal to the degree of the corresponding vertex
C.
The sum of elements in any row is always 1
D.
The sum of elements in any row is equal to the number of vertices

Correct Answer:

Step-by-Step Solution

Insight: The diagonal entry of the Laplacian is the vertex degree, and the off-diagonal entries are -1 for each adjacent vertex.

Exam route: Row sum = $de g (v_{i}) + \sum (- 1) = de g (v_{i}) - de g (v_{i}) = 0$ .

Learning route:

Recall the definition of the Laplacian matrix $L$ : $L_{ii} = de g (v_{i})$ and $L_{ij} = - 1$ if $(v_{i}, v_{j}) \in E$ , else $0$ .
The sum of the elements in row $i$ is the diagonal entry plus the sum of the off-diagonal entries.
There are exactly $de g (v_{i})$ off-diagonal entries equal to $- 1$ in row $i$ .
Sum = $de g (v_{i}) + (- de g (v_{i})) = 0$ .

Answer: The sum of elements in any row is always 0

Question 6 · Engineering Mathematics MCQ

If the determinant of the reduced Laplacian matrix of a connected graph is 12, how many spanning trees does the graph have?

A.
6
B.
12
C.
24
D.
144

Correct Answer:

Step-by-Step Solution

Key idea: Kirchhoff's Matrix Tree Theorem states that the number of spanning trees equals the determinant of any cofactor of the Laplacian matrix.

Step 1: According to Kirchhoff's theorem, $τ (G) = det (L^{'})$ , where $L^{'}$ is the reduced Laplacian matrix (obtained by deleting any one row and one column from the Laplacian).

Step 2: The problem states that $det (L^{'}) = 12$ .

Step 3: Therefore, the number of spanning trees is $τ (G) = 12$ .

Answer: 12.

Question 7 · Engineering Mathematics MCQ

What is the maximum number of edges in a simple disconnected graph with 6 vertices?

A.
10
B.
15
C.
12
D.
9

Correct Answer:

Step-by-Step Solution

Key idea: To maximize edges in a disconnected graph, make one component as large as possible ( $K_{n - 1}$ ) and one isolated vertex ( $K_{1}$ ).

Step 1: The formula is $E_{ma x} = \frac{( n - 1 ) ( n - 2 )}{2}$ .

Step 2: For $n = 6$ : $E_{ma x} = \frac{( 6 - 1 ) ( 6 - 2 )}{2} = \frac{5 \times 4}{2} = 10$ .

Answer: 10.

Question 8 · Engineering Mathematics MCQ

Match the following connected planar graphs with their number of faces (including the outer face):

\begin{array}{ll}

\textbf{Graph} & \textbf{Vertices, Edges} \\

\text{I} & (4, 6) \\

\text{II} & (6, 9) \\

\text{III} & (8, 12)

\end{array}

\begin{array}{ll}

\textbf{Faces} \\

\text{P} & 4 \\

\text{Q} & 5 \\

\text{R} & 6

\end{array}

A.
I-P, II-Q, III-R
B.
I-Q, II-R, III-P
C.
I-P, II-R, III-Q
D.
I-R, II-Q, III-P

Correct Answer:

Step-by-Step Solution

Key idea: This tests Euler's formula $V - E + F = 2$ for connected planar graphs.

Step 1: Apply Euler's formula to each graph:

Step 2: Graph I: $V = 4, E = 6$

$4 - 6 + F = 2 ⟹ F = 4$ → P

Step 3: Graph II: $V = 6, E = 9$

$6 - 9 + F = 2 ⟹ F = 5$ → Q

Step 4: Graph III: $V = 8, E = 12$

$8 - 12 + F = 2 ⟹ F = 6$ → R

Answer: I-P, II-Q, III-R

Question 9 · Engineering Mathematics MCQ

Which of the following statements about the number of matchings $m (n)$ in a path graph $P_{n}$ is TRUE?

A.
$m (n) = 2^{n}$
B.
$m (n) = F_{n + 1}$ , where $F_{k}$ is the $k$ -th Fibonacci number with $F_{1} = 1, F_{2} = 1$
C.
$m (n)$ does not include the empty matching
D.
$m (n) = F_{n}$

Correct Answer:

Step-by-Step Solution

Key idea: This is a statement truth question on the explicit formula for matchings in a path, recognizable because it tests the exact relationship between $m (n)$ and the Fibonacci sequence.

Step 1: Recall the recurrence for $m (n)$ : $m (n) = m (n - 1) + m (n - 2)$ with base cases $m (1) = 1$ and $m (2) = 2$ .

Step 2: Compare this to the Fibonacci sequence $F_{k}$ where $F_{1} = 1, F_{2} = 1, F_{3} = 2, F_{4} = 3, F_{5} = 5, \dots$

Step 3: Check the values:

$m (1) = 1 = F_{2}$
$m (2) = 2 = F_{3}$
$m (3) = 3 = F_{4}$
$m (4) = 5 = F_{5}$

Step 4: The pattern is $m (n) = F_{n + 1}$ .

Answer: $m (n) = F_{n + 1}$

Question 10 · Engineering Mathematics MCQ

How many of the following triples $(V, E, F)$ can represent a connected planar graph?

$(5, 8, 5), (6, 10, 6), (7, 12, 7), (8, 15, 8)$

A.
1
B.
2
C.
3
D.
4

Correct Answer:

Step-by-Step Solution

Key idea: This tests validation using Euler's formula $V - E + F = 2$ for connected planar graphs.

Step 1: Check each triple against $V - E + F = 2$ :

Step 2: $(5, 8, 5)$ : $5 - 8 + 5 = 2$ ✓ Valid

Step 3: $(6, 10, 6)$ : $6 - 10 + 6 = 2$ ✓ Valid

Step 4: $(7, 12, 7)$ : $7 - 12 + 7 = 2$ ✓ Valid

Step 5: $(8, 15, 8)$ : $8 - 15 + 8 = 1 \neq = 2$ ✗ Invalid

Step 6: Count valid triples: 3

Answer: 3

Try a question

Login to view the complete practice questions and solutions

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course

Graph Fundamentals, Trees and Connectivity Practice Questions for GATE CS

Chapter Roadmap: Graph Fundamentals, Trees and Connectivity

Chapter Journey

1. Spanning Tree Enumeration

2. Weighted Spanning Trees

3. Connectivity & Planarity

4. Matchings & Distances

Hero Concept: What is a Spanning Tree?

The Spanning Tree

Graph Fundamentals, Trees and Connectivity: Solved Questions with Step-by-Step Explanations (10 Problems)

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

More practice questions in this unit