Greedy coloring of a countable bounded-degree graph

Enumerate the vertices. At step $j$, at most $\Delta$ previously colored neighbors of $v_j$ can forbid colors. Choose any of the $\Delta+1$ colors that remains. Induction defines a color at every step. For an edge, the later endpoint receives a color different from the earlier endpoint, proving properness. A finite graph uses the same argument with a finite enumeration.

The bound uses the degree, not the number of vertices. No limiting recoloring argument is needed for a countably infinite graph.

• Tait, Introduction to Combinatorics, Proposition 3.1.10 (greedy coloring).