Question 87
For a graph $G$,
$$
\begin{aligned}
\chi_G &= \min \{k : G \text{ has a } k \text{ colouring}\}, \\
\Delta_G &= \max \{\text{degrees of vertices of } G\}.
\end{aligned}
$$
a. Prove that for any simple connected graph $G$, $\chi_G \le \Delta_G + 1$.
b. A regular graph is a graph that every vertex has the same degree. Prove that if a simple connected graph $G$ is not regular, then $\chi_G \le \Delta_G$.
$$
\begin{aligned}
\chi_G &= \min \{k : G \text{ has a } k \text{ colouring}\}, \\
\Delta_G &= \max \{\text{degrees of vertices of } G\}.
\end{aligned}
$$
a. Prove that for any simple connected graph $G$, $\chi_G \le \Delta_G + 1$.
b. A regular graph is a graph that every vertex has the same degree. Prove that if a simple connected graph $G$ is not regular, then $\chi_G \le \Delta_G$.