MathCastle
Graph TheoryChallengeGraph Coloring

Graph Coloring · Challenge problem

The 55-cycle 1-2-3-4-5-11\text{-}2\text{-}3\text{-}4\text{-}5\text{-}1 has χ(C5)=3\chi(C_5)=3. Among the 55 possible "chords" (edges joining two non-adjacent rim vertices: 13,14,24,25,3513,14,24,25,35), for how many does ADDING that single chord to C5C_5 raise the chromatic number above 33?