For any vertex v in a graph H, let the degree of v be the number of vertices w such that \{v, w\} is an edge in H. Let G be an arbitrary graph with maximum degree \Delta. Prove that \chi(G) \leq \Delta+1.
For any vertex v in a graph H, let the degree of v be the number of vertices w such that \{v, w\} is an edge in H. Let G be an arbitrary graph with maximum degree \Delta. Prove that \chi(G) \leq \Delta+1.