Lovász Hamiltonian path conjecture

Imagine a network in which every junction looks the same under a symmetry of the entire network. Can you walk along its links and visit every junction once, without revisiting one? The route may end somewhere different from where it began.[1] [2]

A connected network may have only a few links at each vertex yet have symmetries carrying any vertex to any other. Does this global uniformity force a route that visits every vertex exactly once? Such a graph is called vertex-transitive. For every finite connected simple graph $G$ whose adjacency-preserving automorphisms act transitively on $V(G)$, the target is a path on $|V(G)|$ vertices. This is the Hamiltonian-path question: there are no prescribed endpoints and no required closing edge. Cayley graphs, with group elements joined by chosen generators, form an important subclass, not the entire scope.[1] [2]

Symmetry gives remarkably long routes. The missing step is reaching every last junction. Demanding a round trip is stronger: even the symmetric Petersen graph has no round trip visiting every vertex once.[1] [2]

The new universal result supplies at least n^(1−ε) cycle vertices for each fixed ε>0 and sufficiently large n. It does not remove all omissions. For d=ω(log³n loglogn), Christoph–Hunter–Sudakov obtain (1−o(1))n cycle vertices; that still permits missing vertices and imposes a degree condition.[1] [2]

Symmetry can supply a global organization even when each junction has only a few links. One important example makes group elements into junctions and the allowed operations into links. A route visiting each junction once would order all those elements using only the allowed operations, without repetitions. That connects a local rule for moving between states with an exact listing of the entire state space.[1] [2]

Conditions such as Dirac’s degree threshold guarantee spanning cycles by making a graph densely connected. The symmetry question investigates a different source of global order, applicable even when every vertex has just three neighbors. In the Cayley subclass, a spanning path would enumerate the finite group by successive allowed generator operations. Extending that connection to arbitrary transitive group actions asks whether algebraic uniformity alone organizes the whole graph, rather than merely producing a long route that may omit vertices.[1] [2]