Graph Coloring, Covers, Matrices and Special Graphs Practice Questions for GATE CS

Solve 126+ Graph Coloring, Covers, Matrices and Special Graphs practice 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 (10 Problems)

Question 1 · Engineering Mathematics MCQ

Let $A$ be the adjacency matrix of a simple undirected graph. Which of the following statements is ALWAYS TRUE regarding the matrix $A^{k}$ for any integer $k \geq 1$ ?

A.
The entry $(A^{k})_{ij}$ gives the number of simple paths of length $k$ from $v_{i}$ to $v_{j}$ .
B.
The trace of $A^{k}$ gives the total number of closed walks of length $k$ in the graph.
C.
The sum of all elements in $A^{k}$ is equal to the total number of cycles of length $k$ .
D.
The diagonal entries of $A^{k}$ are always zero for all $k$ .

Correct Answer:

Step-by-Step Solution

Key idea: This is a bounding/statement truth question that tests the fundamental properties of matrix powers and the constraints of graph traversals.

Step 1: Evaluate Option A. $A^{k}$ counts all walks, not just simple paths. Walks allow repeated vertices. Thus, A is false.

Step 2: Evaluate Option B. The trace of a matrix is the sum of its diagonal entries. The diagonal entry $(A^{k})_{ii}$ is the number of closed walks of length $k$ starting and ending at $v_{i}$ . Summing over all $i$ gives the total number of closed walks of length $k$ in the graph. Thus, B is true.

Step 3: Evaluate Option C. The sum of all elements counts all walks of length $k$ , not just cycles. Cycles are simple closed paths. Thus, C is false.

Step 4: Evaluate Option D. For even $k$ , there are closed walks (e.g., $v_{i} \to v_{j} \to v_{i}$ for $k = 2$ ). Thus, diagonal entries are non-zero for even $k$ . D is false.

Answer: B

Question 2 · Engineering Mathematics MCQ

In a simple undirected graph, the entry $(A^{3})_{ii}$ represents the number of walks of length 3 from vertex $v_{i}$ to itself. What is the minimum number of distinct triangles containing $v_{i}$ if $(A^{3})_{ii} = 4$ ?

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

Correct Answer:

Step-by-Step Solution

Key idea: This is a contradiction/minimum question that tests the distinction between walks and simple cycles, specifically how triangles contribute to the diagonal of $A^{3}$ .

Step 1: Recall that a walk of length 3 from $v_{i}$ to $v_{i}$ must be of the form $v_{i} \to v_{j} \to v_{k} \to v_{i}$ .

Step 2: In a simple graph, to return in exactly 3 steps without immediately backtracking (which would require an even length), the vertices $v_{i}, v_{j}, v_{k}$ must be distinct.

Step 3: Thus, every walk of length 3 from $v_{i}$ to $v_{i}$ corresponds to a triangle containing $v_{i}$ .

Step 4: For any specific triangle containing $v_{i}$ , there are exactly 2 distinct walks of length 3: one in clockwise order and one in counter-clockwise order.

Step 5: If $(A^{3})_{ii} = 4$ , and each triangle contributes exactly 2 walks, the number of triangles is $4/2 = 2$ .

Answer: B

Question 3 · Engineering Mathematics MCQ

Match the graph property in List I with its corresponding mathematical value or formula in List II for a simple undirected graph with adjacency matrix $A$ .

List I

P. Number of triangles in $G$

Q. The entry $(A^{3})_{ii}$

R. The trace of $A^{3}$

List II

Total number of closed walks of length 3 in $G$
$Tr (A^{3}) /6$
Number of closed walks of length 3 from $v_{i}$ to $v_{i}$

Select the correct matching from the options below.

A.
P-2, Q-3, R-1
B.
P-1, Q-3, R-2
C.
P-2, Q-1, R-3
D.
P-3, Q-2, R-1

Correct Answer:

Step-by-Step Solution

Key idea: This question tests the exact definitions of matrix powers and the specific formula for counting triangles.

Step 1: The entry $(A^{k})_{ij}$ gives the number of walks of length $k$ from $v_{i}$ to $v_{j}$ . Therefore, $(A^{3})_{ii}$ is the number of closed walks of length 3 starting and ending at $v_{i}$ . This matches Q with 3.

Step 2: The trace of a matrix is the sum of its diagonal entries. Thus, $Tr (A^{3}) = \sum_{i = 1}^{n} (A^{3})_{ii}$ , which is the total number of closed walks of length 3 in the entire graph $G$ . This matches R with 1.

Step 3: A triangle is a simple cycle of length 3. Each triangle generates exactly 6 closed walks of length 3 (3 starting vertices $\times$ 2 directions). To get the number of triangles, we divide the total closed walks of length 3 by 6. This matches P with 2.

Answer: P-2, Q-3, R-1 (Option A)

Question 4 · Engineering Mathematics MCQ

Let $A$ be the adjacency matrix of a simple undirected graph $G$ . If the trace of $A^{3}$ is 42, how many triangles does the graph $G$ contain?

A.
14
B.
21
C.
7
D.
42

Correct Answer:

Step-by-Step Solution

Key idea: The trace of $A^{3}$ counts all closed walks of length 3, but each triangle is counted multiple times.

Step 1: Recall that the trace of $A^{3}$ , denoted $Tr (A^{3})$ , gives the total number of closed walks of length 3 in the graph.

Step 2: In a simple graph, any closed walk of length 3 must be a triangle (since you can't repeat edges or vertices without immediately closing a cycle of length < 3, which isn't allowed in simple graphs).

Step 3: Each triangle ${u, v, w}$ can be traversed as a closed walk of length 3 in exactly 6 ways:

Starting at $u$ : $u \to v \to w \to u$ and $u \to w \to v \to u$
Starting at $v$ : $v \to w \to u \to v$ and $v \to u \to w \to v$
Starting at $w$ : $w \to u \to v \to w$ and $w \to v \to u \to w$

Step 4: Therefore, the number of triangles is $Tr (A^{3}) /6$ .

Step 5: Given $Tr (A^{3}) = 42$ , the number of triangles is $42/6 = 7$ .

Answer: 7

Question 5 · Engineering Mathematics MCQ

A proper $k$ -coloring of a graph $G = (V, E)$ assigns colors such that $c (u) \neq = c (v)$ for all $(u, v) \in E$ . For a star graph $S_{3}$ (1 center, 3 leaves), the number of proper $k$ -colorings is calculated by considering the center and leaves separately. If $k = 3$ , what is the total number of proper 3-colorings?

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

Correct Answer:

Step-by-Step Solution

Key idea: This is a direct application of the proper coloring definition to a specific graph structure (star graph) using casework for the center and leaves.

Step 1: Identify the structure of $S_{3}$ . It has 1 center vertex connected to 3 leaf vertices.

Step 2: Calculate the number of choices for the center vertex. Since there are $k = 3$ colors available, the center can be colored in 3 ways.

Step 3: Calculate the number of choices for the leaf vertices. Each leaf is connected only to the center. Since the center has used 1 color, each leaf can be colored with any of the remaining $k - 1 = 2$ colors.

Step 4: Since there are 3 leaves, and each has 2 independent choices, the number of ways to color the leaves is $2 \times 2 \times 2 = 2^{3} = 8$ .

Step 5: Multiply the choices for the center and the leaves: $3 \times 8 = 24$ .

Answer: C

Question 6 · Engineering Mathematics MCQ

A graph is bipartite if and only if it contains no odd-length cycles. What is the minimum number of edges that must be removed from a complete graph $K_{5}$ to make it bipartite?

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

Correct Answer:

Step-by-Step Solution

Key idea: This is a contradiction-based question. We know the target state (bipartite) has a strict upper bound on edges, and we must find the minimum removals to satisfy this bound.

Step 1: Calculate the total number of edges in the initial graph $K_{5}$ . The formula is $\frac{n ( n - 1 )}{2} = \frac{5 \times 4}{2} = 10$ edges.

Step 2: Determine the maximum number of edges a bipartite graph on 5 vertices can have. From the previous concept, this is $⌊ 5/2 ⌋ \times ⌈ 5/2 ⌉ = 2 \times 3 = 6$ edges (the graph $K_{2, 3}$ ).

Step 3: To make $K_{5}$ bipartite, we must reduce its edge count to at most 6.

Step 4: Calculate the minimum number of edges to remove: $10 - 6 = 4$ edges.

Step 5: Verify that removing 4 edges can indeed leave a bipartite graph. Yes, removing the edges within the partitions of $K_{2, 3}$ (which are $(2 2) + (2 3) = 1 + 3 = 4$ edges) leaves exactly $K_{2, 3}$ , which is bipartite.

Answer: B

Question 7 · Engineering Mathematics MCQ

By considering whether the first and third vertices of a cycle graph $C_{4}$ have the same or different colors, calculate the number of proper 3-colorings of $C_{4}$ .

A.
14
B.
16
C.
18
D.
24

Correct Answer:

Step-by-Step Solution

Key idea: This is a casework question on the chromatic polynomial of $C_{4}$ , requiring careful tracking of color choices based on vertex adjacency.

Step 1: Identify the structure of $C_{4}$ . It has 4 vertices $v_{1}, v_{2}, v_{3}, v_{4}$ in a cycle. We have $k = 3$ colors.

Step 2: Assign colors to $v_{1}$ and $v_{2}$ . $v_{1}$ has 3 choices. $v_{2}$ is adjacent to $v_{1}$ , so it has $3 - 1 = 2$ choices.

Step 3: Casework on $v_{3}$ . $v_{3}$ is adjacent to $v_{2}$ .

Step 4: Case 1: $v_{3}$ has the same color as $v_{1}$ . There is 1 choice for $v_{3}$ . Since $v_{4}$ is adjacent to $v_{3}$ and $v_{1}$ (which are the same color), $v_{4}$ has $3 - 1 = 2$ choices. Total for Case 1: $3 \times 2 \times 1 \times 2 = 12$ .

Step 5: Case 2: $v_{3}$ has a different color from $v_{1}$ . Since $v_{3}$ must differ from $v_{2}$ , and $v_{2}$ differs from $v_{1}$ , there is exactly 1 choice for $v_{3}$ (the third color). Now $v_{4}$ is adjacent to $v_{3}$ and $v_{1}$ , which have different colors. So $v_{4}$ has $3 - 2 = 1$ choice. Total for Case 2: $3 \times 2 \times 1 \times 1 = 6$ .

Step 6: Add the cases: $12 + 6 = 18$ .

Answer: C

Question 8 · Engineering Mathematics MCQ

A graph $G$ consists of three disjoint triangles ( $K_{3}$ ). What is the minimum number of edges that must be removed from $G$ to make it bipartite?

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

Correct Answer:

Step-by-Step Solution

Key idea: This is a contradiction-based question. A graph is bipartite if and only if it contains no odd cycles. We must break all odd cycles with the minimum number of edge removals.

Step 1: Identify the odd cycles in $G$ . The graph consists of three disjoint triangles ( $K_{3}$ or $C_{3}$ ). Each triangle is an odd cycle.

Step 2: To make a triangle bipartite, we must break the cycle. Removing any 1 edge from a triangle converts it into a path of 3 vertices ( $P_{3}$ ), which is a tree and therefore bipartite.

Step 3: Since there are three disjoint triangles, we must remove at least 1 edge from each triangle to destroy all odd cycles.

Step 4: Calculate the minimum total edges to remove: $1 \times 3 = 3$ edges.

Answer: C

Question 9 · Engineering Mathematics MCQ

Let $A$ be the adjacency matrix of a simple undirected graph. What does the entry $(i, j)$ in the matrix $A^{k}$ represent, where $k$ is a positive integer?

A.
The number of simple paths of length $k$ from vertex $v_{i}$ to vertex $v_{j}$ .
B.
The number of walks of length $k$ from vertex $v_{i}$ to vertex $v_{j}$ .
C.
The number of cycles of length $k$ that contain both vertex $v_{i}$ and vertex $v_{j}$ .
D.
The number of edges between vertex $v_{i}$ and vertex $v_{j}$ raised to the power $k$ .

Correct Answer:

Step-by-Step Solution

Key idea: This is a direct formula recall question about the fundamental theorem of adjacency matrices and walk counting.

Step 1: Recall the definition of the adjacency matrix $A$ and the meaning of matrix powers in graph theory.

Step 2: The entry $(A^{k})_{ij}$ is calculated by summing the products of entries along all possible intermediate sequences of $k$ steps.

Step 3: This mathematical operation counts every valid sequence of $k$ edges from $v_{i}$ to $v_{j}$ , which is the exact definition of a walk.

Step 4: Note that walks allow repeated vertices and edges, unlike simple paths or cycles. Therefore, $A^{k}$ counts walks, not simple paths.

Answer: B

Question 10 · Engineering Mathematics MCQ

Consider the following two statements about a simple undirected graph $G$ with $m$ edges and adjacency matrix $A$ :

Assertion (A): The sum of all diagonal entries of $A^{2}$ is $2 m$ .

Reason (R): The diagonal entry $(A^{2})_{ii}$ counts the number of walks of length 2 from $v_{i}$ to $v_{i}$ , which equals the degree of $v_{i}$ , and the sum of degrees of all vertices is $2 m$ .

Which of the following is correct?

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: This is a direct application of the walk-counting property of adjacency matrices combined with the handshaking lemma.

Step 1: By the power rule, $(A^{2})_{ii}$ is the number of walks of length 2 from $v_{i}$ to $v_{i}$ . In a simple graph, a walk of length 2 from $v_{i}$ to $v_{i}$ must go to a neighbor and back. Thus, $(A^{2})_{ii} = de g (v_{i})$ . This makes Reason (R) true.

Step 2: The sum of all diagonal entries of $A^{2}$ is $\sum_{i = 1}^{n} (A^{2})_{ii} = \sum_{i = 1}^{n} de g (v_{i})$ .

Step 3: By the handshaking lemma, the sum of degrees of all vertices in a graph with $m$ edges is $2 m$ . This makes Assertion (A) true.

Step 4: Since (R) correctly explains why the sum is $2 m$ (by linking the matrix entries to degrees, and degrees to $2 m$ ), R is the correct explanation of A.

Answer: A

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 Coloring, Covers, Matrices and Special Graphs Practice Questions 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 (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

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 Coloring, Covers, Matrices and Special Graphs Practice Questions 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 (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

Chromatic Number $χ (G)$