chapter

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

Graph Coloring, Covers, Matrices and Special Graphs notes for GATE CS: 31 study cards covering concepts, formulas, shortcuts and exam traps, plus solved pract

graph coloring covers matrices and special graphs notes

Chapter Roadmap: Discrete Mathematics Graph Theory

Chapter Journey: Graph Structures & Algorithms 1 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. 2 Adjacency Matrices & Walk Counting Focus: Matrix representation, matrix powers for paths, trace for cycles. Goal: Link algebraic properties to graph topology. 3 Minimum Vertex Covers Focus: Covering all edges with a minimal set of vertices. Goal: Understand structural constraints and approximation bounds. 4 Special Graphs & Isomorphism Focus: Petersen graph properties, Hamiltonian and Eulerian paths. Goal: Recognize standard counter-examples and structural equivalence. .smart-card { font-family: system-ui, -apple-system, sans-serif; color: var(--color-text); background: var(--color-bg); padding: 1.5rem; border-radius: 12px; } .timeline { position: relative; padding-left: 1rem; } .timeline-item { display: flex; gap: 1rem; margin-bottom: 0.5rem; } .timeline-marker { flex-shrink: 0; width: 28px; height: 28px; border-radius: 50%; background: var(--color-muted); color: var(--color-text); display: flex; align-items: center; justify-content: center; font-weight: bold; font-size: 0.9rem; } .timeline-item.current .timeline-marker { background: var(--color-primary); color: var(--color-bg); } .timeline-content { flex: 1; } .timeline-content ul { margin: 0.5rem 0 0 0; padding-left: 1.2rem; font-size: 0.9rem; color: var(--color-text); opacity: 0.9; } .timeline-connector { width: 2px; height: 1.5rem; background: var(--color-border); margin-left: 13px; } .badge { display: inline-block; font-size: 0.75rem; padding: 0.15rem 0.5rem; border-radius: 4px; background: color-mix(in srgb, var(--color-primary) 20%, transparent); color: var(--color-primary); margin-left: 0.5rem; vertical-align: middle; }

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. .smart-card { font-family: system-ui, -apple-system, sans-serif; color: var(--color-text); background: var(--color-bg); padding: 1.5rem; border-radius: 12px; } .definition-box { background: color-mix(in srgb, var(--color-primary) 10%, transparent); border-left: 4px solid var(--color-primary); padding: 1rem; border-radius: 0 8px 8px 0; margin: 1rem 0; } .intuition-box { background: color-mix(in srgb, var(--color-muted) 20%, transparent); padding: 1rem; border-radius: 8px; margin-top: 1.5rem; font-style: italic; } h2, h3 { margin-top: 0; } ul { line-height: 1.6; }

Bipartite Graphs are 2-Colorable

Bipartite Graphs ⟺ 2-Colorable Definition: A graph G is bipartite if its vertex set V can be partitioned into two disjoint sets V_{1} and V_{2} such that every edge connects a vertex in V_{1} to one in V_{2} . Key Theorem: G is bipartite ⟺ χ (G) \leq 2 Why? If G is bipartite, assign Color 1 to all v \in V_{1} and Color 2 to all v \in V_{2} . No conflicts exist because there are no edges within V_{1} or within V_{2} . If G is 2-colorable, let V_{1} be vertices with Color 1 and V_{2} be vertices with Color 2. By definition of proper coloring, no edge exists within V_{1} or V_{2} . Thus, G is bipartite. Note: An empty graph (no edges) has χ (G) = 1 and is technically bipartite (one set can be empty). .smart-card { font-family: system-ui, -apple-system, sans-serif; color: var(--color-text); background: var(--color-bg); padding: 1.5rem; border-radius: 12px; } .concept-block, .theorem-block { margin: 1rem 0; padding: 1rem; border-radius: 8px; } .theorem-block { background: color-mix(in srgb, var(--color-primary) 15%, transparent); text-align: center; font-size: 1.1rem; } .note-block { margin-top: 1.5rem; padding: 0.75rem; background: color-mix(in srgb, var(--color-muted) 15%, transparent); border-radius: 6px; font-size: 0.9rem; } ol { line-height: 1.7; padding-left: 1.5rem; }

28 more cards in this chapter

Try a question

Answer it here to see how it works. Nothing is recorded until you sign in.

Question 1

Level 1: Warm-up

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 ?

Question 2

Level 1: Warm-up

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 ?

Question 3

Level 1: Warm-up

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.

Question 4

Level 1: Warm-up

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?

Question 5

Level 1: Warm-up

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?

Question 6

Level 1: Warm-up

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?

Question 7

Level 1: Warm-up

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} .

Question 8

Level 1: Warm-up

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?

Question 9

Level 1: Warm-up

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?

Question 10

Level 1: Warm-up

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?

Free preview ends here

Login to view the complete notes

Creating an account is free. You get the rest of this chapter, step-by-step solutions, and a study plan built around the topics you are actually weak at.

Why MastersUp

Personalised first. High quality throughout.

Most platforms hand everyone the same content. Here the content moves with your performance, topic by topic.

Built around you, not around a syllabus PDF

Every answer you give moves your topic-level intelligence rate. The next question, the next revision card and tomorrow's plan all change with it.

Revision that hits your weak spots

We only revise topics you have actually attempted and are still below the safe bar on — never the same chapter on repeat.

Questions calibrated to the real exam

Each question carries a measured toughness. You are served a rung above your current level, so practice keeps stretching you.

Notes written for recall, not for volume

Full lesson cards for first study, curated short-note cards for the last mile — with derivations, traps and exam patterns marked.

One place for everything

Notes, chapter practice, previous-year questions, test series and full-length papers — all feeding one picture of your preparation.

Honest progress

No vanity streaks. Progress here means chapters mastered and accuracy that held up on harder questions.

Unlock the whole course

Full notes and short notes, the complete question bank with worked solutions, mock tests, full-length papers, and an adaptive plan that rebuilds itself as you improve.

View all plans Start free

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

Graph Coloring, Covers, Matrices and Special Graphs notes for GATE CS: 31 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

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.

Bipartite Graphs are 2-Colorable

Bipartite Graphs $⟺$ 2-Colorable

Definition: A graph

G

is bipartite if its vertex set

V

can be partitioned into two disjoint sets

V_{1}

and

V_{2}

such that every edge connects a vertex in

V_{1}

to one in

V_{2}

Key Theorem:

G is bipartite ⟺ χ (G) \leq 2

Why?

If $G$ is bipartite, assign Color 1 to all $v \in V_{1}$ and Color 2 to all $v \in V_{2}$ . No conflicts exist because there are no edges within $V_{1}$ or within $V_{2}$ .
If $G$ is 2-colorable, let $V_{1}$ be vertices with Color 1 and $V_{2}$ be vertices with Color 2. By definition of proper coloring, no edge exists within $V_{1}$ or $V_{2}$ . Thus, $G$ is bipartite.

Note: An empty graph (no edges) has

χ (G) = 1

and is technically bipartite (one set can be empty).

Odd Cycles Break Bipartiteness

Characterization via Cycles

Theorem: A graph is bipartite if and only if it contains no odd-length cycles.

Logical Deduction

Consider a cycle $C_{n}$ .
If $n$ is even, you can alternate colors $1, 2, 1, 2 \dots$ and close the loop consistently.
If $n$ is odd, alternating $1, 2, 1, 2 \dots$ leads to a conflict at the last edge (the start and end vertices would require different colors but are adjacent).

Odd cycle

C_{5}

showing color clash at the final edge.

Implication for Chromatic Number

If $G$ contains a triangle ( $C_{3}$ ), then $χ (G) \geq 3$ .
If $G$ contains a $C_{5}$ , then $χ (G) \geq 3$ .
Presence of any odd cycle implies $χ (G) > 2$ .

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

graph coloring covers matrices and special graphs notes

Chapter Roadmap: Discrete Mathematics Graph Theory

Chapter Journey: Graph Structures & Algorithms

Hero Concept: Proper Graph Coloring

What is Graph Coloring?

Chromatic Number χ(G)

Bipartite Graphs are 2-Colorable

Bipartite Graphs ⟺ 2-Colorable

Why?

Try a question

Login to view the complete notes

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 Notes 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)

Bipartite Graphs are 2-Colorable

Bipartite Graphs ⟺ 2-Colorable

Why?

Odd Cycles Break Bipartiteness

Characterization via Cycles

Logical Deduction

Implication for Chromatic Number

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 notes in this unit

Chromatic Number $χ (G)$

Bipartite Graphs $⟺$ 2-Colorable

Chromatic Number $χ (G)$

Bipartite Graphs $⟺$ 2-Colorable