MathCastle
Graph TheoryHardGraph Coloring

Graph Coloring · Hard problem

The Möbius ladder M8M_8 has vertices 1,…,81,\ldots,8 arranged in the cycle 1-2-3-4-5-6-7-8-11\text{-}2\text{-}3\text{-}4\text{-}5\text{-}6\text{-}7\text{-}8\text{-}1, together with the 44 "diagonal" edges joining each vertex to the one directly opposite: 15,26,37,4815,26,37,48 (1212 edges in all, every vertex of degree 33). What is χ(M8)\chi(M_8)?