Use greedy vertex coloring algorithm to prove the upper bound of χ

[bremenfallturm]

Homework Statement

Let $e_i(G)$ denote the number of vertices of a graph $G$ whose degree is strictly greater than $i$. Use the greedy algorithm to show that if $e_i(G) \le i+1$ for some $i$, then $\chi(G) \le i+1$ (Discrete Mathematics by Biggs, 2nd Ed, Exercise 15.7.3)

Relevant Equations

Definition of "the greedy algorithm". One such definition (which matches what my book uses) can be found here: https://people.cs.uchicago.edu/~laci/HANDOUTS/greedycoloring.pdf (I also added a screenshot of the definition in my post)

Hi!

I am struggling with the exercise I mentioned under "Homework statement".

The exercise is about a specific "greedy vertex coloring algorithm". One definition (which matches what my book uses) can be found here: https://people.cs.uchicago.edu/~laci/HANDOUTS/greedycoloring.pdf

Here is also a screenshot of the relevant parts of the linked PDF, i.e. the def. of the algorithm:

Sadly I don't have much to show as far as a solution attempt goes, as I am stuck on how to proceed.
I thought that one approach might be to prove that this property of the greedy algorithm is true, given my constraints: $|\left\{c(j)|j<i, j \in \text{adj}(i)\right\}| \le i$, because that implies that the no color $> i+1$ will be picked by the greedy algorithm.
However, I can't figure out a way to prove that.

 

[haruspex]

The trick is to handle the vertices in the right order. Which vertices will be the most problematic? Deal with those first.