Graph Coloring, Covers, Matrices and Special Graphs PYQs for GATE CS

Solve 8+ Graph Coloring, Covers, Matrices and Special Graphs previous year questions for GATE CS with answers and detailed solutions. Free sample questions below.

Chapter Roadmap: Discrete Mathematics Graph Theory

Chapter Journey: Graph Structures & Algorithms

Graph Coloring & Bipartite Graphs Current Topic

Focus: Chromatic number, proper coloring, bipartiteness.
Goal: Determine minimum colors needed; identify 2-colorable graphs.
Weight: High frequency in logic-based questions.

Adjacency Matrices & Walk Counting

Focus: Matrix representation, matrix powers for paths, trace for cycles.
Goal: Link algebraic properties to graph topology.

Minimum Vertex Covers

Focus: Covering all edges with a minimal set of vertices.
Goal: Understand structural constraints and approximation bounds.

Special Graphs & Isomorphism

Focus: Petersen graph properties, Hamiltonian and Eulerian paths.
Goal: Recognize standard counter-examples and structural equivalence.

Hero Concept: Proper Graph Coloring

What is Graph Coloring?

A proper coloring of a graph $G = (V, E)$ is an assignment of colors to vertices such that no two adjacent vertices share the same color.

Formally, a function $c : V \to {1, 2, \dots, k}$ is a proper $k$ -coloring if:

\forall (u, v) \in E, c (u) \neq = c (v)

Chromatic Number $χ (G)$

The smallest integer $k$ for which $G$ has a proper $k$ -coloring.

If $χ (G) = k$ , the graph is $k$ -chromatic.
If $χ (G) \leq k$ , the graph is $k$ -colorable.

Intuition: Think of colors as "resources" or "time slots." Adjacent vertices compete for resources.

χ (G)

tells you the minimum resource pool size required to satisfy all constraints simultaneously.

Graph Coloring, Covers, Matrices and Special Graphs: Solved Questions with Step-by-Step Explanations (8 Problems)

Question 1 · Engineering Mathematics · 2026_Set1 MSQ

Let

G (V, E)

be a simple, undirected graph. A vertex cover of

G

is a subset

V^{'} \subseteq V

such that for every

(u, v) \in E

u \in V^{'}

v \in V^{'}

. Let the size of the smallest vertex cover in

G

k

. Let

S

be any vertex cover of size

k

.

For a vertex

v \in V

, which of the following constraints will always ensure that

v \in S

A.
The degree of $v$ is at least $k + 1$
B.
The vertex $v$ is on a path of length $k + 1$
C.
The vertex $v$ is on a cycle of length $k + 1$
D.
The vertex $v$ is a part of a clique of size $k$

Correct Answer:

["A"]

Step-by-Step Solution

Insight: If a vertex has degree $\geq k + 1$ , excluding it from the vertex cover forces all its neighbors into the cover, requiring at least $k + 1$ vertices, which contradicts the cover size being $k$ .

Exam route: Test the degree condition. If $v$ is not in $S$ , its neighbors must be. If $de g (v) \geq k + 1$ , $∣ S ∣ \geq k + 1$ , a contradiction. Thus $v$ must be in $S$ .

Learning route:

Option A: True. If $v \in / S$ , all $de g (v)$ neighbors must be in $S$ to cover the edges incident to $v$ . Since $de g (v) \geq k + 1$ , this requires $∣ S ∣ \geq k + 1$ , contradicting $∣ S ∣ = k$ . Thus, $v$ must be in $S$ .
Option B: False. Consider a path of length 3 (4 vertices: $a - b - c - d$ ). The minimum vertex cover size is $k = 2$ (e.g., $S = {b, c}$ ). Vertex $a$ is on the path but not in $S$ .
Option C: False. Consider a cycle of length 3 ( $C_{3}$ ). The minimum vertex cover size is $k = 2$ (e.g., $S = {a, b}$ ). Vertex $c$ is on the cycle but not in $S$ .
Option D: False. Consider a clique of size 3 ( $K_{3}$ ). The minimum vertex cover size is $k = 2$ (e.g., $S = {a, b}$ ). Vertex $c$ is part of the clique but not in $S$ .

Question 2 · Engineering Mathematics · 2026_Set1 MSQ

An undirected, unweighted, simple graph

G (V, E)

is said to be 2-colorable if there exists a function

c : V \to {0, 1}

such that for every

(u, v) \in E

c (u) \neq = c (v)

.

Which of the following statements about 2-colorable graphs is/are true?

A.
If $G$ is 2-colorable, then $G$ may contain cycles of odd length
B.
If $G$ is 2-colorable, then $G$ may contain cycles of even length
C.
An optimal algorithm for testing whether $G$ is 2-colorable runs in time $Θ (∣ V ∣ + ∣ E ∣)$ , if $G$ is represented as an adjacency list
D.
An optimal algorithm for testing whether $G$ is 2-colorable runs in time $Θ (∣ E ∣ lo g ∣ V ∣)$ , if $G$ is represented as an adjacency list

Correct Answer:

["B","C"]

Step-by-Step Solution

Insight: 2-colorable graphs are exactly bipartite graphs, which have no odd cycles and can be tested in linear time $Θ (∣ V ∣ + ∣ E ∣)$ using BFS/DFS.

Exam route: Recall the definition of bipartite graphs (no odd cycles) and the standard linear-time BFS algorithm for bipartiteness testing.

Learning route:

Option A: False. By definition, a graph is 2-colorable if and only if it is bipartite, which means it contains NO odd-length cycles.
Option B: True. Bipartite graphs can contain even-length cycles (e.g., $C_{4}$ ).
Option C: True. Testing bipartiteness via BFS or DFS takes $Θ (∣ V ∣ + ∣ E ∣)$ time, which is optimal for adjacency list representation.
Option D: False. $Θ (∣ V ∣ + ∣ E ∣)$ is strictly faster than $Θ (∣ E ∣ lo g ∣ V ∣)$ for connected graphs, making the latter non-optimal.

Question 3 · Engineering Mathematics · 2024_Set2 MCQ

Let $A$ be the adjacency matrix of a simple undirected graph $G$ . Suppose $A$ is its own inverse. Which one of the following statements is always TRUE?

A.
$G$ is a cycle
B.
$G$ is a perfect matching
C.
$G$ is a complete graph
D.
There is no such graph $G$

Correct Answer:

Step-by-Step Solution

Insight: $A = A^{- 1}$ implies $A^{2} = I$ . The diagonal entries of $A^{2}$ represent the degrees of the vertices, so every vertex must have a degree of exactly 1.

Exam route: $A^{2} = I$ means $(A^{2})_{ii} = 1$ for all $i$ . Since $(A^{2})_{ii}$ is the degree of vertex $i$ , every vertex has degree 1. This uniquely defines a perfect matching.

Learning route:

The condition $A = A^{- 1}$ is equivalent to $A^{2} = I$ , where $I$ is the identity matrix.
This means that for every vertex $i$ , the diagonal entry $(A^{2})_{ii} = 1$ .
From the properties of adjacency matrices, $(A^{2})_{ii}$ equals the number of walks of length 2 from vertex $i$ to itself, which is exactly the degree of vertex $i$ in a simple graph.
Therefore, every vertex in the graph must have a degree of exactly 1.
A simple undirected graph where every vertex has degree exactly 1 is, by definition, a perfect matching (a disjoint union of $K_{2}$ components).
Checking the options: A cycle has degree 2. A complete graph has degree $n - 1$ . A perfect matching has degree 1.

Question 4 · Engineering Mathematics · 2024_Set2 NAT

The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. The chromatic number of the following graph is __________

Correct Answer:

2.00

Step-by-Step Solution

Insight: The graph is bipartite if and only if it can be 2-colored without adjacent vertices sharing a color, meaning no odd cycles exist.

Exam route: Attempt a BFS 2-coloring. If no conflicts arise, $χ = 2$ .

Learning route:

Assign Color 1 (Red) to an arbitrary starting vertex, say the top-left vertex $V_{1}$ .
All neighbors of $V_{1}$ must be Color 2 (Blue).
All neighbors of those Blue vertices must be Red.
Continue this alternating assignment. Tracing the provided graph, we find a valid partition: Red = { $V_{1}, V_{4}, V_{5}, V_{8}$ }, Blue = { $V_{2}, V_{3}, V_{6}, V_{7}$ }.
Verify no edges exist between two Red or two Blue vertices. Since a valid 2-coloring exists and the graph has edges, $χ = 2$ .

Question 5 · Engineering Mathematics · 2024_Set1 MSQ

The chromatic number of a graph is the minimum number of colours used in a <i>proper</i> colouring of the graph. Let $G$ be any graph with $n$ vertices and chromatic number $k$ . Which of the following statements is/are always TRUE?

A.
$G$ contains a complete subgraph with $k$ vertices
B.
$G$ contains an independent set of size at least $n / k$
C.
$G$ contains at least $k (k - 1) /2$ edges
D.
$G$ contains a vertex of degree at least $k$

Correct Answer:

["B","C"]

Step-by-Step Solution

Insight: Chromatic number $k$ guarantees a $k$ -critical subgraph (dictating minimum edges) and partitions vertices into $k$ independent sets (bounding maximum independent set size via Pigeonhole Principle).

Exam route: Use Pigeonhole Principle for Option B. Recall $k$ -critical subgraph minimum degree $\geq k - 1$ for Option C. Disprove A and D with standard counterexamples ( $C_{5}$ and $K_{k}$ ).

Learning route:

Option A: False. A graph with $χ = k$ does not necessarily contain a $K_{k}$ . Counterexample: $C_{5}$ has $χ = 3$ but no $K_{3}$ (triangle).
Option B: True. A proper $k$ -coloring partitions $n$ vertices into $k$ independent sets (color classes). By the Pigeonhole Principle, at least one color class must have size $\geq ⌈ n / k ⌉ \geq n / k$ .
Option C: True. Any graph with $χ = k$ contains a $k$ -critical subgraph. A $k$ -critical graph has a minimum degree of at least $k - 1$ and at least $k$ vertices. Thus, the number of edges is at least $\frac{k ( k - 1 )}{2}$ .
Option D: False. A graph with $χ = k$ must have a vertex of degree at least $k - 1$ , but not necessarily $k$ . Counterexample: $K_{k}$ has $χ = k$ , but every vertex has degree exactly $k - 1$ .

Question 6 · Engineering Mathematics · 2022 MSQ

Which of the properties hold for the adjacency matrix $A$ of a simple undirected unweighted graph having $n$ vertices?

A.
The diagonal entries of $A^{2}$ are the degrees of the vertices of the graph.
B.
If the graph is connected, then none of the entries of $A^{n - 1} + I_{n}$ can be zero.
C.
If the sum of all the elements of $A$ is at most $2 (n - 1)$ , then the graph must be acyclic.
D.
If there is at least a 1 in each of $A$ ’s rows and columns, then the graph must be connected.

Correct Answer:

["A"]

Step-by-Step Solution

Insight: The diagonal entries of $A^{2}$ count the number of walks of length 2 from a vertex to itself, which equals its degree in a simple undirected graph.

Exam route: Evaluate $(A^{2})_{ii} = \sum_{j} A_{ij} A_{j i}$ . Since $A$ is symmetric and binary, this simplifies to $\sum_{j} A_{ij}$ , which is the degree of vertex $i$ . Disprove B, C, D with counterexamples.

Learning route:

Option A: True. $(A^{2})_{ii} = \sum_{j} A_{ij} A_{j i}$ . Since $G$ is undirected, $A$ is symmetric ( $A_{j i} = A_{ij}$ ). Since $G$ is simple, $A_{ij} \in {0, 1}$ , so $A_{ij}^{2} = A_{ij}$ . Thus, $(A^{2})_{ii} = \sum_{j} A_{ij} = degree (i)$ .
Option B: False. Consider a star graph with $n = 4$ (center 1, leaves 2, 3, 4). $n - 1 = 3$ . The number of walks of length 3 between leaves 2 and 3 is 0. Thus, $(A^{3} + I)_{23} = 0$ .
Option C: False. Consider a triangle plus an isolated vertex ( $n = 4$ , $∣ E ∣ = 3$ ). The sum of all elements in $A$ is $2∣ E ∣ = 6 \leq 2 (4 - 1) = 6$ . However, the graph contains a cycle (the triangle).
Option D: False. Consider two disjoint triangles ( $n = 6$ ). Every vertex has degree 2, so every row and column has at least one 1. However, the graph is disconnected.

Question 7 · Engineering Mathematics · 2022 MCQ

Consider a simple undirected unweighted graph with at least three vertices. If $A$ is the adjacency matrix of the graph, then the number of 3-cycles in the graph is given by the trace of

A.
$A^{3}$
B.
$A^{3}$ divided by 2
C.
$A^{3}$ divided by 3
D.
$A^{3}$ divided by 6

Correct Answer:

Step-by-Step Solution

Insight: The trace of $A^{3}$ counts all closed walks of length 3. Each triangle is counted exactly 6 times (3 starting vertices $\times$ 2 directions).

Exam route: Recall the formula for counting triangles using the adjacency matrix: $Triangles = \frac{Tr ( A ^{3} )}{6}$ .

Learning route:

The $(i, j)$ entry of $A^{k}$ represents the number of walks of length $k$ from vertex $i$ to vertex $j$ .
The trace of $A^{3}$ is the sum of its diagonal entries, $\sum (A^{3})_{ii}$ . This represents the total number of closed walks of length 3 in the graph.
In a simple graph, any closed walk of length 3 must be a triangle (a 3-cycle), as there are no self-loops or multiple edges.
Each 3-cycle consists of 3 vertices. A closed walk of length 3 can start at any of these 3 vertices and traverse the cycle in 2 directions (clockwise or counter-clockwise).
Therefore, each distinct 3-cycle is counted exactly $3 \times 2 = 6$ times in the trace of $A^{3}$ . To find the number of unique 3-cycles, we must divide the trace by 6.

Question 8 · Engineering Mathematics · 2022 MSQ

The following simple undirected graph is referred to as the Peterson graph.

Which of the following statements is/are TRUE?

A.
The chromatic number of the graph is 3.
B.
The graph has a Hamiltonian path.
C. The following graph is isomorphic to the Peterson graph.
D.
The size of the largest independent set of the given graph is 3. (A subset of vertices of a graph form an independent set if no two vertices of the subset are adjacent.)

Correct Answer:

["A","B","C"]

Step-by-Step Solution

Insight: The Petersen graph is a famous 3-regular, non-planar graph with $χ = 3$ , independence number 4, a Hamiltonian path, but no Hamiltonian cycle.

Exam route: Recall the standard invariant cheat sheet for the Petersen graph: 10 vertices, 15 edges, girth 5, $χ = 3$ , $α = 4$ , Hamiltonian path (yes), Hamiltonian cycle (no).

Learning route:

Option A: True. The Petersen graph contains 5-cycles (odd), so $χ \geq 3$ . It is 3-colorable, so $χ = 3$ .
Option B: True. While it lacks a Hamiltonian cycle, it is well-known to possess a Hamiltonian path.
Option C: True. The second graph is a standard alternative drawing of the Petersen graph (it is 3-regular, has 10 vertices, 15 edges, and girth 5).
Option D: False. The independence number (largest independent set) of the Petersen graph is 4, not 3.

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 Coloring, Covers, Matrices and Special Graphs PYQs for GATE CS

Chapter Roadmap: Discrete Mathematics Graph Theory

Chapter Journey: Graph Structures & Algorithms

Hero Concept: Proper Graph Coloring

What is Graph Coloring?

Chromatic Number $χ (G)$

Graph Coloring, Covers, Matrices and Special Graphs: 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

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 Coloring, Covers, Matrices and Special Graphs PYQs for GATE CS

Chapter Roadmap: Discrete Mathematics Graph Theory

Chapter Journey: Graph Structures & Algorithms

Hero Concept: Proper Graph Coloring

What is Graph Coloring?

Chromatic Number χ(G)

Graph Coloring, Covers, Matrices and Special Graphs: 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

Chromatic Number $χ (G)$