Let $G$ be a $d$-regular graph with $n$ vertices. Prove that $\chi_G \ge n/(n-d)$.
$d$-regular means that $\left(\forall v \in V\right) \left(\text{deg}(v) = d \right)$. $\chi_G$ is the chromatic number of $G$ (the minimal number of colors needed to color the graph $G$ so that no two adjacent vertices have the same color).
This is an exercise from a book about graph theory but I can't understand one thing. The answer given in the book is too vague in my opinion:
Let $c_i$ be the number of vertices having color $i$, where $1 \le i \le \chi_G$, then $c_i \le n - d$. Thus $n = c_1 + \cdots + c_{\chi_G} \le \chi_G (n-d)$, therefore $\chi_G \ge n/(n-d)$.
Why exactly $c_i \le n - d$? A detailed explanation with a picture would be greatly appreciated.
$\endgroup$2 Answers
$\begingroup$We know we can color $G$ with $\chi_G$ colors, so we do so, creating color classes $C_1, \dots, C_{\chi_G}$. Let $c_i = |C_{i}|$ be the size of each of these color classes. Now let $v \in C_i$ be any vertex of any color class. This vertex $v$ has $d$ neighbors, and these neighbors must be in a different color class than $v$. This $C_i$ cannot contain these $d$ neighbors, so $c_i = |C_i| \leq n - d$.
Now that we have bounds on the sizes of each of the color classes, we note that every vertex is contained in exactly one color class, giving $$ n = c_1 + \cdots + c_{\chi_G} $$ and the rest follows.
Note that requirement that the graph be $d$-regular may be dropped. We only need minimum degree $d$. Also note that the complete bipartite graph shows that equality can be met.
$\endgroup$ $\begingroup$Let $v$ be a vertex of color $i.$ Then there are $d$ vertices which can't have color $i,$ namely, the $d$ neighbors of $v.$ (We know there are $d$ of them because $G$ is $d$-regular.) There are $n$ vertices in the graph, and $d$ of them can't have color $i,$ that leaves (at most) $n-d$ vertices of color $i.$ Therefore, $c_i\le n-d.$
$\endgroup$
