Graph Coloring I
What is the chromatic number of the above graph?
The chromatic number of this graph is 3. First, observe that 3 colors are sufficient. Two colors are enough for the vertices \((a, b, c, d, e, \text{ and } f)\),
if we alternate their colors moving in a circle around the
figure. A third color can be used for the vertex, \(g\), in the
center, and this completes the coloring.
Second, 3 colors are necessary. This is because the graph
contains a triangle (for example, the one formed by \(a\), \(b\), and \(g\)), and any triangle needs 3 colors.