Let $(d_1,d_2, \ldots , d_n)$ be a sequence of vertices degrees in graph $G$. Prove that $\chi(G) \le \max_{i \in \{1,2,\ldots,n \}} \min \{d_i + 1, i \}$.
Inequality with chromatic number and degrees of vertices
graph theory
graph theory
Let $(d_1,d_2, \ldots , d_n)$ be a sequence of vertices degrees in graph $G$. Prove that $\chi(G) \le \max_{i \in \{1,2,\ldots,n \}} \min \{d_i + 1, i \}$.
Best Answer
Every min produces a result out of two possibilities: either the value $i$ or the value $d_i+1$ is obtained (if the two coincides, we consider it as if $i$ were chosen). Let $j$ be the last index where $i$ is produced as a result (rather than $d_i+1$). Then you can colour the first $j$ vertices with all different colours, and finish the rest greedily.