chromatic number and maximum degree

chi(G) counts the fewest colors needed to properly color a graph; Delta is the largest degree any single vertex has.

The chromatic number $\chi(G)$ is the minimum number of colors in a proper vertex coloring of $G$ . The maximum degree $\Delta(G) = \max_v \deg(v)$ upper-bounds it: $\chi(G) \le \Delta(G)+1$ always, and $\chi(G)\le\Delta(G)$ except for complete graphs and odd cycles (Brooks' theorem).