MathCastle
Graph TheoryHardEulerian and Hamiltonian Graphs

Eulerian and Hamiltonian Graphs · Hard problem

Three triangles share a single hub vertex 00: triangle 0-1-20\text{-}1\text{-}2, triangle 0-3-40\text{-}3\text{-}4, and triangle 0-5-60\text{-}5\text{-}6 (nine edges total, no edges between the triangles except through 00). A closed route crosses every edge of this graph exactly once. Not counting the very last step back to 00, how many times does the route pass through the hub vertex 00?