Graph Fundamentals, Trees and Connectivity PYQs for GATE CS

Solve 8+ Graph Fundamentals, Trees and Connectivity previous year 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 (8 Problems)

Question 1 · Engineering Mathematics · 2026_Set2 MCQ

Consider a complete graph

K_{n}

with

n

vertices

(n > 4)

. Note that multiple spanning trees can be constructed over

K_{n}

. Each of these spanning trees is represented as a set of edges. The Jaccard coefficient between any two sets is defined as the ratio of the size of the intersection of the two sets to the size of the union of the two sets.

Which one of the following options gives the lowest possible value for the Jaccard coefficient between any two spanning trees of

K_{n}

A.
$\frac{1}{n}$
B.
$\frac{1}{2 n - 3}$
C.
0
D.
$\frac{1}{n - 1}$

Correct Answer:

Step-by-Step Solution

Key idea: This is a Jaccard coefficient minimization question on spanning trees of $K_{n}$ , recognisable because it asks for the lowest possible Jaccard value between two spanning trees.

Why this method applies: The Jaccard coefficient $J (T_{1}, T_{2}) = \frac{∣ E _{1} \cap E _{2} ∣}{∣ E _{1} \cup E _{2} ∣}$ . To minimize $J$ , we minimize the intersection. The question is whether two edge-disjoint spanning trees can exist in $K_{n}$ .

Step 1: Each spanning tree of $K_{n}$ has exactly $n - 1$ edges. Two disjoint trees need $2 (n - 1)$ distinct edges.

Step 2: $K_{n}$ has $(2 n) = \frac{n ( n - 1 )}{2}$ edges. For two disjoint spanning trees to exist, we need:

$\frac{n ( n - 1 )}{2} \geq 2 (n - 1) ⟹ \frac{n}{2} \geq 2 ⟹ n \geq 4$

Step 3: Since the problem states $n > 4$ , the condition $n \geq 4$ is satisfied. Therefore, $K_{n}$ contains two completely edge-disjoint spanning trees.

Step 4: When $E_{1} \cap E_{2} = \emptyset$ , the Jaccard coefficient is:

$J = \frac{0}{2 ( n - 1 ) - 0} = 0$

Step 5: Check the options. Option C gives 0, which is achievable.

Answer: C

Question 2 · Engineering Mathematics · 2026_Set1 NAT

Let $G$ be an undirected graph, which is a path on 8 vertices. The number of matchings in $G$ is ______. (answer in integer)

Correct Answer:

34.00

Step-by-Step Solution

Insight: The number of matchings in a path graph follows the Fibonacci recurrence $M (n) = M (n - 1) + M (n - 2)$ .

Exam route: Base cases $M (1) = 1, M (2) = 2$ . Build the sequence: 3, 5, 8, 13, 21, 34.

Learning route:

Step 1: Define $M (n)$ as the total number of matchings (including the empty matching) in a path $P_{n}$ .

Step 2: Formulate the recurrence by considering the first vertex $v_{1}$ :

Case 1: $v_{1}$ is unmatched. The remaining $n - 1$ vertices form $P_{n - 1}$ , giving $M (n - 1)$ matchings.
Case 2: $v_{1}$ is matched. It must be matched to $v_{2}$ . The remaining $n - 2$ vertices form $P_{n - 2}$ , giving $M (n - 2)$ matchings.
Total: $M (n) = M (n - 1) + M (n - 2)$ .

Step 3: Establish base cases.

$M (1) = 1$ (only the empty matching).
$M (2) = 2$ (empty matching, or the single edge).

Step 4: Compute up to $n = 8$ :

$M (3) = 1 + 2 = 3$

$M (4) = 2 + 3 = 5$

$M (5) = 3 + 5 = 8$

$M (6) = 5 + 8 = 13$

$M (7) = 8 + 13 = 21$

$M (8) = 13 + 21 = 34$ .

Question 3 · Engineering Mathematics · 2024_Set2 MSQ

Let $G$ be an undirected connected graph in which every edge has a positive integer weight. Suppose that every spanning tree in $G$ has even weight. Which of the following statements is/are TRUE for every such graph $G$ ?

A.
All edges in $G$ have even weight
B.
All edges in $G$ have even weight OR all edges in $G$ have odd weight
C.
In each cycle $C$ in $G$ , all edges in $C$ have even weight
D.
In each cycle $C$ in $G$ , either all edges in $C$ have even weight OR all edges in $C$ have odd weight

Correct Answer:

["D"]

Step-by-Step Solution

Key idea: This is a spanning tree parity question, recognisable because it asks which structural properties must hold when every spanning tree has even weight.

Why this method applies: The condition "every spanning tree has even weight" triggers the Parity Invariance Theorem. By the exchange property, swapping edges between two spanning trees preserves parity, which forces all edges within any 2-edge-connected component to share the same parity.

Step 1: Recall the exchange property. If $T_{1}$ and $T_{2}$ are spanning trees and we swap edge $e \in T_{2} ∖ T_{1}$ for edge $f$ in the cycle created, then $w (T_{1}^{'}) - w (T_{1}) = w (e) - w (f)$ . Since both trees have even weight, $w (e) \equiv w (f) (mod 2)$ .

Step 2: Apply to cycles. Every cycle is a 2-edge-connected subgraph. Any two edges in a cycle lie on a common cycle, so they can be swapped via exchange operations. Therefore, all edges in any cycle must share the same parity — either all even or all odd.

Step 3: Evaluate each option.

Option A: "All edges even." FALSE. Counter-example: $K_{3}$ with all edges weight 1 (odd). Every spanning tree has 2 edges, weight $= 1 + 1 = 2$ (even). Edges are odd, not even.

Option B: "All edges even OR all edges odd." FALSE. Different 2-edge-connected components can have different parities. Example: two triangles joined by a bridge, one with all-even edges and one with all-odd edges (3 vertices, odd count). All spanning trees still have even total weight.

Option C: "In each cycle, all edges even." FALSE. Same $K_{3}$ counter-example: the cycle has all odd edges.

Option D: "In each cycle, all edges even OR all edges odd." TRUE. This is exactly the Parity Invariance Theorem applied to cycles.

Answer: D

Question 4 · Engineering Mathematics · 2024_Set1 NAT

The number of spanning trees in a complete graph of 4 vertices labelled A, B, C, and D is __________

Correct Answer:

16.00

Step-by-Step Solution

Key idea: This is a direct Cayley's formula question, recognisable because it asks for the number of spanning trees in a complete graph with labeled vertices.

Why this method applies: The graph is $K_{4}$ (complete, 4 labeled vertices). Cayley's formula gives the exact count without needing Kirchhoff's matrix method.

Step 1: Recall Cayley's formula. For a complete graph $K_{n}$ with $n$ labeled vertices, the number of spanning trees is $τ (K_{n}) = n^{n - 2}$ .

Step 2: Substitute $n = 4$ .

$τ (K_{4}) = 4^{4 - 2} = 4^{2} = 16$

Step 3: Verify by enumeration logic. $K_{4}$ has 6 edges. A spanning tree needs 3 edges. The total number of 3-edge subsets is $(3 6) = 20$ . Of these, 4 form cycles (the four triangles in $K_{4}$ ), leaving $20 - 4 = 16$ spanning trees. This confirms the result.

Answer: 16.00

Question 5 · Engineering Mathematics · 2022 NAT

Let $G (V, E)$ be a directed graph, where $V = {1, 2, 3, 4, 5}$ is the set of vertices and $E$ is the set of directed edges, as defined by the following adjacency matrix $A$ .

$A [i] [j] = {1, 0, 1 \leq j \leq i \leq 5 otherwise$

$A [i] [j] = 1$ indicates a directed edge from node $i$ to node $j$ . A directed spanning tree of $G$ , rooted at $r \in V$ , is defined as a subgraph $T$ of $G$ such that the undirected version of $T$ is a tree, and $T$ contains a directed path from $r$ to every other vertex in $V$ . The number of such directed spanning trees rooted at vertex $5$ is_____________.

Correct Answer:

24.00

Step-by-Step Solution

Insight: The graph is a DAG with edges pointing from higher to lower indices. Each non-root vertex simply chooses one parent from the available higher-indexed vertices.

Exam route: Vertex 4 has 1 choice (5). Vertex 3 has 2 choices (4,5). Vertex 2 has 3 choices. Vertex 1 has 4 choices. Total = $1 \times 2 \times 3 \times 4 = 24$ .

Learning route:

Step 1: Understand the edge directions. $A [i] [j] = 1$ for $j \leq i$ means edges go from $i$ to $j$ . This is a Directed Acyclic Graph (DAG) where edges strictly decrease in index.

Step 2: Define the arborescence condition. A directed spanning tree rooted at 5 requires every other vertex to have exactly one incoming edge from a vertex that is reachable from 5. Since edges only go down, any valid parent choice guarantees reachability from 5.

Step 3: Count choices for each vertex's incoming edge:

Vertex 4: Can only receive from 5. (1 choice)
Vertex 3: Can receive from 4 or 5. (2 choices)
Vertex 2: Can receive from 3, 4, or 5. (3 choices)
Vertex 1: Can receive from 2, 3, 4, or 5. (4 choices)

Step 4: Multiply the independent choices: $1 \times 2 \times 3 \times 4 = 24$ .

Question 6 · Engineering Mathematics · 2022 NAT

Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the maximum number of edges it can have is ____________.

Correct Answer:

36.00

Step-by-Step Solution

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

Exam route: $E_{ma x} = (2 n - 1) = (2 9) = 36$ .

Learning route:

Step 1: A disconnected graph with $n$ vertices must have at least two components. Let their sizes be $k$ and $n - k$ .

Step 2: To maximize edges, both components must be complete graphs. The total edges are $E = (2 k) + (2 n - k)$ .

Step 3: The function $f (x) = (2 x)$ is strictly convex. The sum of convex functions under a fixed sum constraint is maximized at the extreme boundaries.

Step 4: Set $k = 1$ and $n - k = 9$ . The maximum edges are $(2 1) + (2 9) = 0 + 36 = 36$ .

Question 7 · Engineering Mathematics · 2021_Set1 NAT

In an undirected connected planar graph $G$ , there are eight vertices and five faces. The number of edges in $G$ is __________.

Correct Answer:

11.00

Step-by-Step Solution

Insight: Euler's formula for connected planar graphs directly relates vertices, edges, and faces.

Exam route: $V - E + F = 2 ⟹ 8 - E + 5 = 2 ⟹ E = 11$ .

Learning route:

Step 1: Identify the graph properties. The graph is undirected, connected, and planar.

Step 2: Recall Euler's formula for connected planar graphs: $V - E + F = 2$ .

Step 3: Substitute the given values. We have $V = 8$ vertices and $F = 5$ faces (including the outer face).

Step 4: Solve for $E$ :

$8 - E + 5 = 2$

$13 - E = 2$

$E = 11$ .

Question 8 · Engineering Mathematics · 2021_Set1 MCQ

Let

G = (V, E)

be an undirected unweighted connected graph. The diameter of

G

is defined as:

diam (G) = u, v \in V max {the length of shortest path between u and v}

Let

M

be the adjacency matrix of

G

.
Define graph

G_{2}

on the same set of vertices with adjacency matrix

N

, where

N_{ij} = {10 if M_{ij} > 0 or P_{ij} > 0, where P = M^{2} otherwise

Which one of the following statements is true?

A.
$diam (G_{2}) \leq ⌈ diam (G) /2 ⌉$
B.
$⌈ diam (G) /2 ⌉ < diam (G_{2}) < diam (G)$
C.
$diam (G_{2}) = diam (G)$
D.
$diam (G) < diam (G_{2}) \leq 2 diam (G)$

Correct Answer:

Step-by-Step Solution

Insight: The matrix $N$ defines the square of the graph $G^{2}$ , where edges connect vertices at distance 1 or 2 in $G$ .

Exam route: In $G^{2}$ , each step covers up to 2 steps of $G$ . Thus, $d_{G^{2}} (u, v) = ⌈ d_{G} (u, v) /2 ⌉$ . The diameter is $⌈ diam (G) /2 ⌉$ , which satisfies $\leq ⌈ diam (G) /2 ⌉$ .

Learning route:

Step 1: Analyze the adjacency matrix $N$ . $N_{ij} = 1$ if $M_{ij} > 0$ (distance 1) or $(M^{2})_{ij} > 0$ (distance 2). This means $G_{2}$ is exactly the graph square $G^{2}$ .

Step 2: Relate distances. A shortest path of length $k$ in $G$ can be traversed in $G^{2}$ by taking steps of length 2. The number of steps required is $⌈ k /2 ⌉$ . Thus, $d_{G_{2}} (u, v) = ⌈ d_{G} (u, v) /2 ⌉$ .

Step 3: Relate diameters. The diameter of $G_{2}$ is the maximum distance in $G_{2}$ , which is $max_{u, v} ⌈ d_{G} (u, v) /2 ⌉ = ⌈ diam (G) /2 ⌉$ .

Step 4: Evaluate options. Since $diam (G_{2}) = ⌈ diam (G) /2 ⌉$ , it is strictly true that $diam (G_{2}) \leq ⌈ diam (G) /2 ⌉$ . Option A is correct.

Try a question

Login to view the complete previous-year 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 PYQs 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 (8 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

More previous year questions (pyqs) in this unit