GATE CS 2023 Q45 — Graphs: Connectivity, Matching, Colouring

Let us analyze each option step-by-step to determine the correct statements.

Option A: Proper Vertex Coloring

A vertex coloring is proper if no two adjacent vertices share the same color.

• At each step $i$, the greedy algorithm assigns to $v_i$ the smallest color $j \in \mathbb{N}$ that is not already assigned to any of its neighbors.
• This explicitly guarantees that $v_i$ will have a different color from all its already-colored neighbors.
• Since this condition is maintained for every vertex, the resulting coloring is guaranteed to be a proper coloring.

Thus, Option A is TRUE.

Option B: Upper Bound of $\Delta(G) + 1$ Colors

• The maximum degree of any vertex in the graph is $\Delta(G)$.
• When we color any vertex $v_i$, it can have at most $\Delta(G)$ neighbors. Therefore, at most $\Delta(G)$ colors can be excluded from selection.
• By the Pigeonhole Principle, among the first $\Delta(G) + 1$ positive integers, there must be at least one color that is not used by any neighbor of $v_i$.
• Consequently, the algorithm will never need a color larger than $\Delta(G) + 1$.

Thus, Option B is TRUE.

Option C: Upper Bound of $\Delta(G)$ Colors

This is not always true. Consider a complete graph $K_3$ (a triangle):

• The maximum degree is $\Delta(K_3) = 2$.
• Any proper coloring of $K_3$ requires $3$ colors.
• Here, the number of colors used is $3 > \Delta(G)$.

Thus, Option C is FALSE.

Option D: Equality to the Chromatic Number $\chi(G)$

The greedy coloring algorithm is highly sensitive to the ordering of the vertices and does not always yield an optimal coloring (the chromatic number $\chi(G)$).

Consider a path graph $P_4$ with vertices $a - b - c - d$ and chromatic number $\chi(P_4) = 2$:

• Suppose we order the vertices as: $a, d, b, c$.
• Color $a$: No neighbors colored yet $\implies \text{color}(a) = 1$.
• Color $d$: No neighbors colored yet $\implies \text{color}(d) = 1$.
• Color $b$: Neighbor $a$ has color $1 \implies \text{color}(b) = 2$.
• Color $c$: Neighbors $b$ (color 2) and $d$ (color 1) are colored $\implies \text{color}(c) = 3$.

The algorithm uses $3$ colors, which is strictly greater than $\chi(P_4) = 2$.

Thus, Option D is FALSE.