Let G be a simple, finite, undirected graph with vertex set \v1, , vn\. Let (G) denote the maximum degree of G and let N = \1, 2, \ denote the set of all possible colors. Color the vertices of G using the following greedy strategy: for i = 1, , n color(vi) \j N : no neighbour of vi is colored j\ Which of the following statements is/are TRUE? A) This procedure results in a proper vertex coloring of G. B) The number of colors used is at most (G) + 1. C) The number of colors used is at most (G). D) The number of colors used is equal to the chromatic number of G.

Official answer: A) This procedure results in a proper vertex coloring of G.; B) The number of colors used is at most (G) + 1.. Explanation: Let us analyze the given greedy coloring procedure step-by-step: 1. Statement (A) is TRUE: At each step i, the vertex vi is assigned the smallest color j N that has not been assigned to any of its adjacent vertices that have already been colored. Consequently, no two adjacent vertices ever receive the same color, guaranteeing a proper vertex coloring of G. 2. Statement (B) is TRUE: The maximum degree of any vertex in G is (G). Therefore, each vertex vi has at most (G) neighbors. When vertex vi is being colored, at most (G) distinct colors are unavailable. In the set of the first (G) + 1 colors, \1, 2, , (G) + 1\, there must always be at least one available color. Hence, the greedy coloring algorithm will use at most (G) + 1 colors. 3. Statement (C) is FALSE: For a complete graph Kn, the maximum degree is (Kn) = n - 1. Since every pair of vertices is connected, n = (Kn) + 1 colors are required. Thus, the greedy algorithm will use (G) + 1 colors, which is strictly greater than (G). 4. Statement (D) is FALSE: The number of colors used by greedy coloring depends heavily on the ordering of the vertices and is not guaranteed to achieve the chromatic number (G). For instance, for a path graph P4 with vertices u1, v1, u2, v2 and edges (u1, v1), (v1, u2), (u2, v2), if the vertices are ordered as u1, u2, v1, v2, the greedy coloring uses 3 colors even though (P4) = 2. Therefore, statements A and B are correct.

A) This procedure results in a proper vertex coloring of G.

B) The number of colors used is at most (G) + 1.

C) The number of colors used is at most (G).

D) The number of colors used is equal to the chromatic number of G.

Engineering Mathematics · Graph Theory

Official IIT answer key · IIT Kanpur · Audited Aug 2026

Take topic test

GATE CSE 2023 Q55 · MSQ · 2 marks

Let $G$ be a simple, finite, undirected graph with vertex set $\{v_1, \ldots, v_n\}$ . Let $\Delta(G)$ denote the maximum degree of $G$ and let $\mathbb{N} = \{1, 2, \ldots\}$ denote the set of all possible colors. Color the vertices of $G$ using the following greedy strategy: for $i = 1, \ldots, n$ $\text{color}(v_i) \leftarrow \min\{j \in \mathbb{N} : \text{ no neighbour of } v_i \text{ is colored } j\}$ Which of the following statements is/are TRUE?

Select one or more options

Key concept

Graph Theory

Step-by-step verified solution

Examiner trap & misconception

Topic notes

How GATE tests Graph Theory

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.

Full Graph Theory guide →

More on Graph Theory

All 21 questions on Graph Theory →

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.

Engineering Mathematics · Graph Theory

Official IIT answer key · IIT Kanpur · Audited Aug 2026

Take topic test

GATE CSE 2023 Q55 · MSQ · 2 marks

Let $G$ be a simple, finite, undirected graph with vertex set $\{v_1, \ldots, v_n\}$ . Let $\Delta(G)$ denote the maximum degree of $G$ and let $\mathbb{N} = \{1, 2, \ldots\}$ denote the set of all possible colors. Color the vertices of $G$ using the following greedy strategy: for $i = 1, \ldots, n$ $\text{color}(v_i) \leftarrow \min\{j \in \mathbb{N} : \text{ no neighbour of } v_i \text{ is colored } j\}$ Which of the following statements is/are TRUE?

Select one or more options

Key concept

Graph Theory

Step-by-step verified solution

Examiner trap & misconception

Topic notes

How GATE tests Graph Theory

Full Graph Theory guide →

More on Graph Theory

All 21 questions on Graph Theory →

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.

Step-by-step verified solution

Check you can still solve Graph Theory under a clock

More from GATE CSE 2023

More on Graph Theory

Step-by-step verified solution

Check you can still solve Graph Theory under a clock

More from GATE CSE 2023

More on Graph Theory

Step-by-step verified solution

Check you can still solve Graph Theory under a clock

More from GATE CSE 2023

More on Graph Theory

Share this solution

Step-by-step verified solution

Check you can still solve Graph Theory under a clock

More from GATE CSE 2023

More on Graph Theory

Share this solution