Question 60

Label the $8$ vertices clockwise around the outer octagon as $v_0, v_1, v_2, v_3, v_4, v_5, v_6, v_7$ (with $v_0, v_1$ at the top, $v_2, v_3$ on the right, $v_4, v_5$ at the bottom, and $v_6, v_7$ on the left). Partition the vertices into two sets by index parity:

Inspecting all $16$ edges of the graph:

• The $8$ outer cycle edges $(v_i, v_{i+1 \bmod 8})$ each connect an even index to an odd index.
• The $2$ vertical chords are $(v_0, v_5)$ and $(v_1, v_4)$ (even to odd).
• The $2$ horizontal chords are $(v_7, v_2)$ and $(v_6, v_3)$ (odd to even).
• The $4$ diagonal chords are $(v_0, v_3), (v_2, v_5), (v_4, v_7), (v_6, v_1)$ (even to odd).

Since every edge has one endpoint in $A$ and one endpoint in $B$, the graph is bipartite (in fact, it is isomorphic to $K_{4,4}$). Because it has at least one edge, its chromatic number is $2$.