Proof of $\chi(G)\leq 1+\max_i\min\{d_i,i-1\}$ in graph theory

Question

I am learning a coloring theorem in graph theory:

If a graph $G$ has degree sequence $d_1\geq\cdots\geq d_n$, then $\chi(G)\leq 1+\max_i\min\{d_i,i-1\}$.

The proof in the book consists of 4 sentences:

1. We apply greedy coloring to the vertices in nonincreasing order of degree.
2. When we color the $i$th vertex $v_i$, it has at most $\min\{d_i,i-1\}$ earlier neighbors, wo at most this many colors appear on its earlier neighbors.
3. Hence the color we assign to $v_i$ is at most $1+\min\{d_i,i-1\}$.
4. This holds for each vertex, so we maximize over $i$ to obtain the upper bound on the maximum color used.

---

The greedy coloring relative to a vertex ordering $v_1,\cdots,v_n$ of $V(G)$ is obtained by coloring vertices in the order $v_1,\cdots,v_n$, assigning to $v_i$ the smallest-indexed color not already used on its lower-indexed neighbors.

---

I don't understand the first sentence in the proof: Where do we use the nonincreasing order of degree in the rest of the proof?

Answer 1

In context "greedy coloring" must mean something like:

1. Assign colors to vertices starting with the ones with the highest degree and ending with the ones of low degree.
2. For each vertex, give it the lowest-numbered color that has not yet been assigned to any of its neighbors.

The nonincreasing degree order is not actually used in the prof -- without that condition, the proof would work equally well to prove:

If a graph $G$ has nodes of degree $d_1, d_2, \ldots, d_n$ then $\chi(G)\le 1+\max_i \min(d_i,i-1)$.

The point of arranging the vertices with higher degree first is that this gives the best opportunity for $\max_i\min(d_i,i-1)$ to be a small number, and therefore gives a stronger bound on the chromatic number.

The key is the $\min(d_i, i-1)$. You want to prevent this from becoming large -- that is, you want to avoid any vertex where $d_i$ and $i-1$ are both large numbers. The simplest way to do that is to make sure that vertices with a large $d_i$ have as small an $i$ as you can give them -- that is, vertices with high degree should come first in the list.