From Notices of the AMS
On Hamilton Cycles in Graphs Defined by Intersecting Set Systems
![(a) Exchange Gray code for 2-element subsets of~[8] obtained by restricting the binary reflected Gray code in~$Q_8$ to level~2; (b) Hamilton cycle in~$K_{9,3}$ via the Chen-F\](/images/baranyai-bw.jpg)
by Torsten Mütze
Communicated by Emilie Purvine
Introduction
In 1857 the Irish mathematician William Rowan Hamilton invented a puzzle whose goal is to find a cycle in the graph of the dodecahedron that visits every vertex exactly once. He dubbed it the 'Icosian game,' as the resulting cycle has exactly twenty ('icosa' in ancient Greek) edges and vertices. In honor of Hamilton, a cycle that visits every vertex of a graph exactly once is now called a Hamilton cycle. The dodecahedron has the interesting property that it looks the same from the point of view of any vertex. Formally, it is vertex-transitive, i.e., any two vertices can be mapped onto each other by an automorphism of the graph.
In 1970 Lovász raised a conjecture which can be considered a highly advanced version of the Icosian game. Specifically, he conjectured that every connected vertex-transitive graph admits a Hamilton cycle, apart from five exceptional graphs, which are a single edge?
- Also in Notices
- A feeling for Khovanov homology
- Differential Equations for Continuous-Time Deep Learning
