Question 55

Proper Coloring: At step $i$, vertex $v_i$ is assigned the minimum color $j \in \mathbb{N}$ that is not assigned to any already-colored neighbour of $v_i$. By construction, no two adjacent vertices receive the same color. Thus, the procedure produces a valid, proper vertex coloring (Statement A is TRUE).

Maximum Colors Used: Every vertex $v_i$ has at most $\Delta(G)$ neighbours in $G$, so at most $\Delta(G)$ distinct colors can be forbidden when choosing a color for $v_i$. In the set of colors $\{1, 2, \dots, \Delta(G) + 1\}$, at least one color is guaranteed to be available by the Pigeonhole Principle. Hence the greedy algorithm never uses more than $\Delta(G) + 1$ colors (Statement B is TRUE).

Statements C and D: For complete graphs $K_n$, $\chi(K_n) = \Delta + 1 = n$, so $\le \Delta$ does not hold in general (C is FALSE). Furthermore, greedy coloring depends heavily on vertex ordering and can use more colors than the optimal chromatic number $\chi(G)$ (D is FALSE).