AI-Assisted Construction and Proof of Directed Hamiltonian Cycles

From an Open Construction Problem to Human–AI Collaboration

A long-disputed directed Hamiltonian cycle construction problem recently produced a notable result. A well-known computer scientist, after years of work on an open question about directed Hamiltonian cycles, used general-purpose large language models and intelligent coding tools to obtain a unified construction that applies to all odd parameters. Human researchers then supplied a rigorous mathematical proof. The point is not merely that “AI produced an answer,” but that it illustrated a reusable research path: humans define the problem and the verification criteria; AI performs high-dimensional search and generates candidate constructions; programs enumerate instances and hunt for counterexamples; and mathematical proof finally closes the argument.

The basic definition is simple: given a directed graph, is there a directed cycle that visits every vertex exactly once? If so, the graph has a Hamiltonian cycle. The hard part is a unified construction—not a search on one concrete graph, but a provable method for an entire parameterized family. Existence proofs can be indirect; constructive proofs must say how edges are drawn, how vertices are ordered, why nothing is repeated or omitted, and why the walk does not close early. That bar for logical rigor is far higher than ordinary heuristic search.

In the original work, AI explored ideas such as fiber decomposition and serpentine constructions and used properties of group-action graphs to form candidates. Researchers then proved the schemes and showed that, under a stated equivalence, there are 760 solutions. For even parameters, another class of intelligent coding tools later produced constructions, and the related programs were released. The technical thread is abstracted below.

Why Finding One Cycle Does Not Solve the Construction Problem

For a fixed-size digraph, Hamiltonian cycles can be sought by backtracking, constraint satisfaction, integer programming, or heuristics. A parameterized family is different: the parameter (m) may be any odd integer, and the vertex set and edges change with (m). Search results on a few instances do not prove the claim for all (m).

There are at least four layers of difficulty:

1. Global cycle constraint. Each vertex appears exactly once and the walk closes. Locally valid edges need not yield a single global cycle.
2. Symmetry and repeated structure. The family is typically regular; ignoring symmetry inflates the search space.
3. Boundary conditions. Odd and even (m) often have different parity obstacles and cannot be shifted naively.
4. Countability and verifiability. Constructions must be related by a clear equivalence so that rotations, reversals, or automorphisms are not counted twice.

A valid scheme must be parameterizable, proven to cover every vertex, proven to have no proper subcycles, and checkable by enumeration.

Fiber Decomposition: Global Constraints Become Layered Ones

Fiber decomposition treats vertices not as an unordered set but as layers (fibers) defined by an invariant. Let (V) be the vertex set and (\pi: V \to B) a projection that splits (V) into fibers (F_b). Edges between fibers follow a rule; edges inside a fiber follow a controlled order.

The Hamiltonian cycle then splits into two subproblems:

• Inter-fiber paths: an order of visiting fibers so that entries and exits match.
• Intra-fiber paths: an order that consumes every vertex in a fiber and lines up entry and exit ports.

If the internal order is well designed, the global cycle is a combination of a fiber sequence and a serpentine sequence inside each fiber. “Every vertex once” reduces to “every vertex once inside each fiber, and each fiber visited once.”

Engineering-wise this is a familiar decomposition: invariants shrink state space; local rules guarantee global properties. Analogies include sharding, compiler basic blocks, and graph contraction/expansion.

Serpentine Construction: Port Matching and a Single Cycle

Fiber decomposition is not enough. Traversing every fiber in the same direction easily produces several small cycles instead of one covering cycle. A serpentine construction alternates direction: enter a fiber at one end, leave at the other; enter the next fiber in reverse so inter-fiber ports stay staggered.

Illustrative pseudocode (structure only, not a complete implementation):

function build_odd_scheme(m):
    seq = []
    for layer in range(m):
        if layer % 2 == 0:
            order = internal_order_forward(layer)
        else:
            order = internal_order_backward(layer)
        seq.extend(order)
    return seq
function verify(m, seq):
    assert len(seq) == vertex_count(m)
    assert len(set(seq)) == vertex_count(m)
    for i in range(len(seq)):
        assert is_directed_edge(seq[i], seq[(i + 1) % len(seq)])

The checks are: sequence length equals the number of vertices, and the set of vertices has the same size (each vertex once); consecutive vertices, including the wrap-around, are directed edges. Serpentine order makes the enter–traverse–leave ports predictable and turns the risk of subcycles into a local pattern that can be inspected.

Group-Action Graphs and Generator Sequences

The original work also used group-action graphs. If vertices are elements of an algebraic structure and edges come from generators or transformations, a Hamiltonian cycle corresponds to a generator sequence whose partial products visit every element once. Fibers may correspond to subgroups, cosets, or orbits.

Construction then depends on algebraic properties of the sequence rather than coordinates. Covering the vertex set without early repetition yields both construction and proof. For odd (m), alternating patterns can avoid periodic collapse; for even (m), the same patterns may hit bipartition obstacles or close early and need extra handling.

The transferable lesson is: recast a combinatorial construction as an algebraic sequence problem, enumerate small instances to find patterns, then prove generality.

Proof, Counting, and Program Verification

AI candidates are not theorems. A proof typically checks:

• Coverage: every vertex appears at least once;
• Uniqueness: every vertex appears at most once;
• Legality: consecutive vertices (including first and last) are directed edges;
• Single cycle: one cycle, not several disjoint subcycles;
• Universality: the argument holds for every odd (m > 1), not only small cases.

Under a defined equivalence, the original work counted 760 solutions. Counting also needs programs: generate parameterized candidates, test Hamiltonicity, then deduplicate by rotation, reversal, or automorphism. Without equivalence, counts depend on representation and are meaningless. The pipeline can be fixed as generate–verify–normalize–deduplicate–emit a certificate.

Even (m) was not solved in full generality at first. Later tools produced even-case constructions, showing that AI search can help on different branches, while humans still set proof goals and verification standards. What matters for practitioners is a reproducible verification loop, not any one model.

Implications and Risk Boundaries for Engineering

Three takeaways for algorithm engineering and research software:

1. AI as a candidate-space searcher. Split constructions into checkable constraints; let models propose patterns; let programs discard counterexamples quickly.
2. Keep proof and testing separate. Tests find bugs; they do not replace proofs. Proofs give universality; they do not replace implementation checks.
3. Record intermediate states and equivalence classes. Multi-round exploration produces variants; normalize and deduplicate or counts and claims become unreliable.

Risks remain: generative models may output constructions that look plausible but cannot be proved; boundary parameters are easy to miss; counting can double-count; port mappings can differ between pseudocode and real code. AI-assisted mathematical or algorithmic constructions should pass small-scale enumeration, counterexample search, formal checks, and human proof.

Closing

The episode is not about AI replacing researchers. It is about a change in tools: general models expand search; coding assistants speed enumeration; humans formalize problems, write proofs, and own the conclusions. The reusable method is the closed loop of decompose–construct–verify–prove–count. New tools matter only when they yield conclusions that are verifiable, reproducible, and explainable.