What are common examiner traps in Graph Theory?

Forgetting to include the source vertex s in the final summation Evaluating vertices out of topological order, leading to incorrect maximal values when multiple paths merge Adding edge weights instead of multiplying them according to the defined path metric rule Arithmetic errors when computing intermediate products with large weight multipliers Confusing the Hamiltonian cycle requirement (visiting every vertex exactly once) with Eulerian circuit (visiting every edge exactly once). Assuming a graph is Hamiltonian merely because it is 2-connected, ignoring forced smaller cycles created by multiple degree-2 vertices sharing identical neighbor sets. Forgetting that an odd number of vertices in a bipartite or grid graph prohibits a Hamiltonian cycle. Assuming |E| ≤ n - 1 guarantees acyclicity without confirming connectivity (e.g., disjoint union of C3 and an isolated vertex has |E| = 3 ≤ 4 - 1 but contains a cycle). Assuming minimum degree ≥ 1 (at least one non-zero entry in each row/column) implies graph connectivity (e.g., K2 ∪ K2 is disconnected). Assuming odd/even walk parity reachability ensures all entries in An-1 + In are non-zero for connected bipartite graphs. Confusing the general upper bound of planar vertex colouring (4) with specific planar sub-classes like triangle-free (3) or bipartite planar (2). Confusing vertex overlap with edge overlap (spanning trees always share all n vertices, but their edge sets can be completely disjoint). Assuming two spanning trees must share at least one edge even when n ≥ 4. Ignoring constraints on n (e.g., n > 4) which guarantee the existence of edge-disjoint spanning trees. Confusing Hamiltonian Path (visiting all vertices without closing) with Hamiltonian Cycle (closed tour), especially on the Petersen graph. Assuming the greedy coloring algorithm always uses exactly the minimum number of colors (G) (greedy coloring is order-dependent and can require up to + 1). Off-by-one errors when applying Euler's formula n - m + f = 1 + k versus n - m + f = 2 on disconnected or multi-component graphs. Forgetting that Cayley's formula nn-2 applies strictly to labeled trees, not unlabeled isomorphism classes. Assuming maximum independent set size (G) equals ⌊ n/2 ⌋ or 3 on Petersen graph instead of the correct value 4. Confusing the number of edges in the original graph G with the number of edges in the DFS spanning forest EF. Off-by-one errors by assuming the graph is fully connected (EF = n - 1) instead of accounting for multiple disjoint components (EF = n - k). Incorrectly adding k instead of subtracting k in EF = n - k, leading to n + EF or other arithmetic missteps. Confusing total faces F with bounded interior faces (Fbounded = F - 1). Assuming (G) = k implies the presence of a complete subgraph Kk (cliques imply high chromatic number, but high chromatic number does not imply a clique, e.g., C5). Forgetting that each 3-cycle is counted 6 times in trace(A3) due to 3 starting vertices and 2 traversal directions. Neglecting isolated vertices (di = 0) during manual graphic sequence reductions. Assuming every graph with (G) = k must have a vertex with degree ≥ k, rather than degree ≥ k - 1.

GATE CSE Graph Theory PYQs

Medium yield9.9% of Engineering Mathematics

In GATE CS, graph theory under Engineering Mathematics emphasizes structural properties, algebraic relationships, and topological invariants of simple undirecte… Read the guide

Take topic test

Questions: 21
Asked: since 2012
Total marks: 38
Marks / paper: 1.5

21 GATE CSE Graph Theory PYQs with solutions, from Engineering Mathematics. Browse all GATE CSE PYQs.

Questions

Every official paper that asked this topic, newest first.

What GATE tests in Graph Theory

Concepts, patterns, formulas and traps distilled from past papers.

In GATE CS, graph theory under Engineering Mathematics emphasizes structural properties, algebraic relationships, and topological invariants of simple undirected graphs. Questions frequently evaluate planar graph relationships using Euler's formula, chromatic numbers and edge coloring bounds (Vizing's theorem, independent set bounds), and degree-based properties (Handshaking lemma, Havel-Hakimi theorem). The focus has steadily migrated from direct formula applications to structural reasoning and algebraic characterizations such as matrix powers.

Core concepts

Directed Acyclic Graphs (DAGs)
Topological sorting / topological traversal order
Dynamic programming on DAGs
Path product optimization
Source-to-vertex reachable paths
Hamiltonian cycle existence and structural necessary conditions
Edge-forcing from low-degree vertices (degree-2 vertices forcing both incident edges)
Subcycle elimination / premature cycle closure
Grid graph (Pm × Pn) Hamiltonicity
Distinction between Hamiltonian cycle (vertex-traversal) and Eulerian circuit (edge-traversal)
Planar graph vertex colouring and chromatic number
Adjacency matrix representation of simple undirected graphs
Powers of adjacency matrices and walk counts (Ak)
Graph connectivity and degree constraints
Acyclicity vs edge count bounds (|E| ≤ n-1)
Properties of complete graphs Kn
Edge count and structure of spanning trees (n-1 edges)
Edge-disjoint spanning trees (spanning tree packing)
Jaccard similarity coefficient applied to discrete structures
Forests and Trees (Vertex-to-edge relation in k-component acyclic graphs)
Planar Graphs, Face Bounds, and Euler's Formula
Handshaking Lemma and Minimum/Maximum Degree Relations
Chromatic Number (G) and Proper Vertex Coloring
Greedy Coloring Algorithm and Worst-Case Color Bounds
Independence Number (G) and Maximum Independent Sets
Hamiltonian Paths vs Hamiltonian Cycles
Graph Isomorphism and Girth/Degree Verification
Cayley's Tree Formula for Labeled Graphs
Connected components of an undirected graph
DFS spanning tree and spanning forest
Tree edge counting invariant (e = v - 1 per tree component)
Planar graphs and Euler's formula
Bounded vs unbounded faces in planar embeddings
Vertex colouring, chromatic number (G), and independent sets
Edge colouring, chromatic index '(G), and Vizing's theorem
Graphic degree sequences and Havel-Hakimi theorem
Bipartite graph recognition and 2-colorability
Self-complementary graphs and complement edge counts
Adjacency matrix powers (Ak)ij and trace properties for closed walks

Recurring question patterns

DAG Path Optimization with Custom Metric
OccasionalNAT2 marks2021
A directed acyclic graph with edge weights is given, along with a custom path metric (e.g., product of edge weights) and an aggregation rule (e.g., maximum score from a source vertex). Candidates compute vertex-level scores via topological order relaxation and return an aggregate sum across all vertices.
Visual Graph Hamiltonicity / Traversal Feasibility
OccasionalMCQ2 marks2026
Given one or more visual graph representations, determine whether a closed traversal visiting every vertex exactly once (Hamiltonian cycle) exists by checking structural properties like grid dimensions or forced subcycles from degree-2 vertices.
Fundamental Graph Invariants and Theorems
OccasionalNAT1 marks2016
Direct retrieval or evaluation of fundamental bounds and theorems on graph classes, such as chromatic numbers or vertex-colouring requirements for planar graphs.
Adjacency Matrix Structural and Spectral Properties
OccasionalMSQ2 marks2022
Multi-statement verification testing properties of graph adjacency matrices, powers of adjacency matrices (number of walks), vertex degrees, edge sums, and connectivity.
Extremal Overlap / Similarity Metric on Graph Subgraphs
RareMCQ2 marks2026
Given a standard graph class (e.g., $K_n$ with $n > 4$ ) and a family of subgraphs (e.g., spanning trees), find the minimum or maximum value of a similarity metric (e.g., Jaccard coefficient) by determining if edge-disjoint configurations exist.
Structural Counting and Invariant Relationships
CommonMCQ2 marks2014
Questions that evaluate edge, vertex, face, or component relationships using fundamental theorems like Euler's planar formula, Handshaking Lemma, or tree/forest decomposition formulas.
Special/Named Graph Property Verification
OccasionalMSQ2 marks2022
Multi-statement verification (typically MSQ) assessing several graph parameters—such as chromatic number, Hamiltonian paths/cycles, graph isomorphism, and independence number—on well-known graphs (e.g., Petersen graph, complete bipartite graphs).
Graph Coloring and Greedy Bounds
OccasionalMSQ2 marks2023
Analyzing bounds and correctness of vertex coloring procedures, comparing maximum degree $\Delta(G)$ , chromatic number $\chi(G)$ , and upper bounds from greedy algorithms.
Spanning Tree Enumeration
CommonNAT1 marks2024
Direct numerical calculation of the number of spanning trees in labeled graphs using Cayley's formula or standard reduction rules.
DFS / BFS Spanning Forest Edge-Component Relation
RareNAT2 marks2024
Given the total number of vertices $n$ in an undirected graph and the total number of edges in its traversal spanning forest (or tree edges), find the number of connected components $k$ using the invariant $E_F = n - k$ .
Planar Graph Invariants via Euler's Formula
CommonNAT1.5 marks2021, 2015, 2012
Given vertices, edges, face-degree restrictions, or bounded/unbounded face distinctions, compute an unknown parameter using Euler's formula and face-edge handshaking.
Graph Colouring and Chromatic Bounds
Commonmixed2 marks2024, 2020
Determine the vertex chromatic number $\chi(G)$ or edge chromatic index $\chi^{\prime}(G)$ of a given graph, or identify universal theoretical inequalities involving color classes and independent sets.
Degree Sequences and Handshaking Sums
Occasionalmixed2 marks2014
Test whether a sequence of non-negative integers is graphic using Havel-Hakimi or degree counts, or calculate the total number of edges in a structured coordinate/grid graph.
Isomorphism and Complementary Graphs
OccasionalNAT2 marks2014
Find parameter values (such as vertex count $n$ ) where a graph class is self-complementary or isomorphic to a derived graph.
Algebraic Graph Properties & Walk Counting
RareMCQ2 marks2022
Relate powers and trace of the adjacency matrix $A^k$ to paths, closed walks, and small subgraph counts (such as triangles/3-cycles).

Formulas GATE uses

Max-Product Path Recurrence on DAG

Q(v) = \max_{(u, v) \in E} \{ Q(u) \times w(u, v) \}

Used to compute optimal path quality-scores for each vertex in a DAG starting from a base case $Q(\mathbf{s}) = 1$ .

Hamiltonicity of Grid Graphs

P_m \times P_n \text{ is Hamiltonian} \iff m, n \ge 2 \text{ and } m \cdot n \equiv 0 \pmod 2

Determining if a rectangular 2D mesh/grid graph contains a Hamiltonian cycle.

Degree Constraint in a Hamiltonian Cycle

\deg_{H}(v) = 2 \quad \forall v \in V(G)

Checking forced edge inclusion when a vertex has degree 2 in $G$ , which can lead to premature subcycles.

Four Colour Theorem

\chi(G) \le 4$ for any planar graph $G

Used to find the upper bound on the minimum number of colours required to vertex-colour any arbitrary planar graph.

Diagonal Entries of Adjacency Matrix Square

(A^2)_{ii} = \sum_{k=1}^n A_{ik}^2 = \sum_{k=1}^n A_{ik} = \text{deg}(v_i)

Used to determine that the diagonal entries of $A^2$ in a simple undirected graph represent the degrees of the vertices (number of closed walks of length 2).

Sum of Elements of Adjacency Matrix (Handshaking Lemma)

\sum_{i=1}^n \sum_{j=1}^n A_{ij} = \sum_{i=1}^n \text{deg}(v_i) = 2|E|

Used to relate the total sum of matrix entries to total edge count and evaluate acyclicity conditions.

Jaccard Coefficient for Edge Sets

J(T_1, T_2) = \frac{|T_1 \cap T_2|}{|T_1 \cup T_2|}

Used to compute the similarity ratio between the edge sets of two subgraphs.

Edge Bound for $k$ Edge-Disjoint Spanning Trees in $K_n$

k(n - 1) \le \frac{n(n - 1)}{2} \implies n \ge 2k

Used to establish the condition on $n$ under which two ( $k=2, n \ge 4$ ) or more edge-disjoint spanning trees can be packed into a complete graph.

Forest Edge Formula

|E| = n - k

Used to compute the total number of edges in a forest with $n$ vertices partitioned into $k$ connected components.

Handshaking Lemma

\sum_{v \in V} \deg(v) = 2|E| \ge n \cdot \delta(G)

Used to relate sum of vertex degrees, minimum degree $\delta$ , and edge count.

Euler's Formula for Planar Graphs

n - m + f = 1 + k

Used to relate vertices ( $n$ ), edges ( $m$ ), and faces ( $f$ ) for a planar graph with $k$ connected components (reduces to $n - m + f = 2$ for connected planar graphs).

Greedy Coloring Degree Upper Bound

\chi(G) \le \Delta(G) + 1

Used to bound the number of colors assigned by the standard sequential greedy coloring algorithm.

Cayley's Formula for Spanning Trees

\tau(K_n) = n^{n-2}

Used to calculate the number of spanning trees in a labeled complete graph $K_n$ on $n$ vertices.

Number of Edges in a Spanning Forest

E_F = n - k

Used to find the number of connected components $k$ , number of vertices $n$ , or total tree edges $E_F$ in a DFS/BFS spanning forest of an undirected graph.

Edges in a Tree Component

e_i = n_i - 1

Used when analyzing individual connected components of a spanning forest where each component $i$ has $n_i$ vertices.

Face-Edge Handshaking Relation

\sum_{i=1}^{F} \text{deg}(F_i) = 2E

Used when each face is bounded by a fixed or minimal number of boundary edges (e.g., $3F \le 2E$ for maximal planar graphs).

Complement Graph Edge Count

|E(\overline{G})| = \frac{n(n-1)}{2} - |E(G)|

Used when evaluating self-complementary graphs or complements of standard graphs like cycles $C_n$ .

3-Cycle Counting via Adjacency Matrix

\text{Number of 3-cycles} = \frac{\text{trace}(A^3)}{6}

Used to count triangles in a simple undirected graph from its unweighted adjacency matrix $A$ .

Vizing's Theorem (Edge Colouring)

\Delta(G) \le \chi^{\prime}(G) \le \Delta(G) + 1

Used to bound and determine the chromatic index (minimum edge colours) based on the graph's maximum degree $\Delta(G)$ .

Independence Number Lower Bound from Chromatic Number

\alpha(G) \ge \left\lceil \frac{n}{\chi(G)} \right\rceil

Used in theoretical bounds relating graph order $n$ , chromatic number $k$ , and maximum independent set size $\alpha(G)$ .

Examiner traps in Graph Theory

Forgetting to include the source vertex s in the final summation
Evaluating vertices out of topological order, leading to incorrect maximal values when multiple paths merge
Adding edge weights instead of multiplying them according to the defined path metric rule
Arithmetic errors when computing intermediate products with large weight multipliers
Confusing the Hamiltonian cycle requirement (visiting every vertex exactly once) with Eulerian circuit (visiting every edge exactly once).
Assuming a graph is Hamiltonian merely because it is 2-connected, ignoring forced smaller cycles created by multiple degree-2 vertices sharing identical neighbor sets.
Forgetting that an odd number of vertices in a bipartite or grid graph prohibits a Hamiltonian cycle.
Assuming |E| ≤ n - 1 guarantees acyclicity without confirming connectivity (e.g., disjoint union of C3 and an isolated vertex has |E| = 3 ≤ 4 - 1 but contains a cycle).
Assuming minimum degree ≥ 1 (at least one non-zero entry in each row/column) implies graph connectivity (e.g., K2 ∪ K2 is disconnected).
Assuming odd/even walk parity reachability ensures all entries in An-1 + In are non-zero for connected bipartite graphs.
Confusing the general upper bound of planar vertex colouring (4) with specific planar sub-classes like triangle-free (3) or bipartite planar (2).
Confusing vertex overlap with edge overlap (spanning trees always share all n vertices, but their edge sets can be completely disjoint).
Assuming two spanning trees must share at least one edge even when n ≥ 4.
Ignoring constraints on n (e.g., n > 4) which guarantee the existence of edge-disjoint spanning trees.
Confusing Hamiltonian Path (visiting all vertices without closing) with Hamiltonian Cycle (closed tour), especially on the Petersen graph.
Assuming the greedy coloring algorithm always uses exactly the minimum number of colors (G) (greedy coloring is order-dependent and can require up to + 1).
Off-by-one errors when applying Euler's formula n - m + f = 1 + k versus n - m + f = 2 on disconnected or multi-component graphs.
Forgetting that Cayley's formula nn-2 applies strictly to labeled trees, not unlabeled isomorphism classes.
Assuming maximum independent set size (G) equals ⌊ n/2 ⌋ or 3 on Petersen graph instead of the correct value 4.
Confusing the number of edges in the original graph G with the number of edges in the DFS spanning forest EF.
Off-by-one errors by assuming the graph is fully connected (EF = n - 1) instead of accounting for multiple disjoint components (EF = n - k).
Incorrectly adding k instead of subtracting k in EF = n - k, leading to n + EF or other arithmetic missteps.
Confusing total faces F with bounded interior faces (Fbounded = F - 1).
Assuming (G) = k implies the presence of a complete subgraph Kk (cliques imply high chromatic number, but high chromatic number does not imply a clique, e.g., C5).
Forgetting that each 3-cycle is counted 6 times in trace(A3) due to 3 starting vertices and 2 traversal directions.
Neglecting isolated vertices (di = 0) during manual graphic sequence reductions.
Assuming every graph with (G) = k must have a vertex with degree ≥ k, rather than degree ≥ k - 1.

How questions are asked

Visual DAG diagram computation (NAT)
Visual graph property check (identifying Hamiltonian cycles across multiple diagrams)
Word problem mapping to graph traversal definitions
Fill-in-the-blank numerical evaluation for graph invariant bounds
Multi-statement evaluation of graph algebraic and topological properties
Extremal value optimization on subgraph edge sets
Direct closed-form formula selection
Inequality derivation combining Handshaking Lemma and Euler's formula
Multi-statement verification of graph invariants on standard named graphs
Algorithm correctness and bound analysis for graph coloring
Direct integer computation via counting formula (NAT)
Numerical calculation of graph components given vertex count and spanning forest edge count (NAT)
Planar face / edge arithmetic (Euler's formula computation)
Graphic degree sequence validation (Havel-Hakimi test)
Grid / coordinate graph edge counting via Handshaking Lemma
Graph chromatic index / number determination for custom constructed graphs
Theoretical multi-statement verification on graph coloring properties (MSQ)
Matrix representation property evaluation (walks and cycle counts via powers of A)

Paper trends

Introduction of custom algebraic path metrics (multiplicative path score rather than standard additive shortest/longest path) tested via 2-mark NAT visual diagram questions.
2021
Graph traversal concepts are contextualized as real-world routing/salesperson scenarios requiring direct visual inspection of small-to-moderate sized graphs.
2026
Shifted from a direct single-value theoretical recall question (1-mark NAT on chromatic bounds) to a rigorous multi-select question (2-mark MSQ) probing structural matrix properties and counterexamples.
2022, 2016
Introduction of interdisciplinary set-similarity definitions (e.g., Jaccard coefficient) applied to graph edge sets and spanning tree properties.
2026
Shift from single-correct structural derivation MCQs to multi-select questions (MSQs) requiring comprehensive analysis across multiple independent graph properties simultaneously.
2023, 2022, 2014
Inclusion of algorithmic discrete math questions (e.g., analyzing greedy vertex coloring behavior and performance guarantees).
2023
Direct evaluation of labeled tree counting using exact closed formulas appearing in low-mark NAT format.
2024
Recent papers use NAT format for graph structural properties combined with traversal concepts (DFS spanning forest), requiring candidates to apply component-tree counting without needing explicit graph visualization.
2024
Shift from standard 1-mark Euler formula MCQs toward 2-mark NATs and theoretical MSQs probing deeper structural properties of chromatic numbers and independent sets.
2024, 2021, 2015, 2012
Introduction of algebraic graph theory concepts (trace of adjacency matrix powers for cycle counting) alongside traditional combinatorial graph theory.
2022
Continued reliance on NAT format for numerical structural graph parameters (edge counts, chromatic numbers, vertices in self-complementary graphs).
2024, 2021, 2020, 2015, 2014

Difficulty notes

Medium difficulty is driven by the number of vertices (requiring careful step-by-step dynamic programming along multiple branching and merging paths) and the need to sum over all 9 vertices without calculation errors.