gpt 6 astra ultra attempt on Math-1084

Matchings extend to Hamiltonian cycles in hypercubes

Definitions and mathematical statement

For an integer $d\geq2$, the $d$-dimensional hypercube $Q_d$ is the simple graph with vertex set $\{0,1\}^d$. Two bit vectors are adjacent exactly when they differ in one coordinate. Thus $Q_d$ has $2^d$ vertices and degree $d$ at every vertex. A matching is a set $M\subseteq E(Q_d)$ whose edges have pairwise disjoint endpoint sets. The empty matching is allowed, and a matching need not cover all vertices.

A Hamilton cycle is a simple cycle passing through every vertex of $Q_d$ exactly once. To extend the matching means to find such a cycle $C$ containing each prescribed matching edge: \[ M\subseteq E(C). \] The conjecture asks whether this is possible for every integer $d\geq2$ and every matching $M$ of $Q_d$.

Equivalently, the task is to cyclically order all binary vectors so consecutive vectors differ in one coordinate, while requiring the endpoints of every edge of $M$ to appear consecutively in that cyclic order. Prescribed edges may point in different coordinate directions and may have any total size up to $2^{d-1}$. No choice of orientation of the matching is imposed. The lower bound on $d$ is necessary under the ordinary simple-cycle convention, since $Q_1$ is a single edge. A theorem for perfect matchings alone would not directly address all matchings required here.

Short English statement

Can every collection of pairwise disjoint hypercube edges be included in one cycle visiting all hypercube vertices?

Research attempt

Scope and process.

GPT-6 Astra Ultra, 1 October 2026. The catalogue formulation is retained above. This attempt checks the original problem and primary literature, proves the restricted claims stated below, and identifies the exact limit of its conclusions. Reproved facts are not claimed as novel results.

Literature and attack.

Fink and Mütze's checked version of 16 April 2025 [S3] proves that every matching extends to a cycle visiting at least two thirds of the hypercube vertices. That statement is weaker than the spanning target. Our argument proves the target for every matching using only one coordinate direction and then tests a common attempted reduction through perfect matchings. Vertices are binary strings; toggling one coordinate is an edge, and a matching may be empty.

A cyclic Gray order.

For $r\ge2$, list all $r$-bit strings in binary-reflected Gray order $x_0,\ldots,x_{2^r-1}$. This is a cyclic order of the cube vertices with consecutive strings differing in one coordinate. Here is a direct inductive construction: prefix the $(r-1)$-bit Gray list by zero, then prefix its reversal by one. Adjacency holds within each half by induction, across the middle because only the prefix changes, and between the last and first because their suffixes are equal. The initial two-bit order is $00,01,11,10$. Thus no Hamiltonicity theorem is being assumed without a construction.

Using every edge in one direction.

Fix the last coordinate of $Q_d$, and put $N=2^{d-1}$. For $d\ge3$, use the cyclic Gray order $x_0,\ldots,x_{N-1}$ of $Q_{d-1}$. At every even index $i$, traverse the two vertices in the order \[ (x_i,0),(x_i,1), \] and at every odd index in the order \[ (x_i,1),(x_i,0). \] Concatenate these pairs cyclically. Inside each pair the last coordinate changes. Between pairs the last coordinate agrees and $x_i,x_{i+1}$ are adjacent. Since $N$ is even, the last pair ends in layer zero and closes to the first vertex $(x_0,0)$ along the Gray closing edge. Every cube vertex occurs once. This is therefore a Hamilton cycle containing every edge parallel to the last coordinate.

Any matching contained in that coordinate direction is a subset of this cycle. Coordinate permutations prove the same assertion for every direction. For $d=2$, the unique four-cycle contains both edges of either direction, providing the omitted base case directly. The construction works for every subset, regardless of its size, including a full coordinate perfect matching.

Why enlarging an arbitrary matching to a perfect one fails.

Consider $Q_3$ and the matching \[ M=\{001\!-!011,\ 010\!-!110,\ 100\!-!101\}. \] Its six endpoints are distinct. The two unmatched vertices are $000$ and $111$, which are not adjacent. Hence $M$ cannot be enlarged, by adding cube edges, to a perfect matching. In particular, even a theorem about extending every perfect matching would not, by itself, handle this $M$ through a perfect-matching completion.

This obstruction is to the reduction, not to the conjecture: the cyclic list \[ 000,001,011,010,110,111,101,100 \] is a Hamilton cycle containing all three required edges. Each consecutive pair differs in precisely one bit, including the closing pair. A Hamilton cycle has two alternating perfect matchings, but a prescribed matching contained in it can use edges from both alternating classes. Confusing these two assertions would incorrectly rule out this example.

Verification and general gap.

The script scripts/check_attempt_batch02_graphs_2026_10_01.py constructs the woven cycles for dimensions two through eight, checks every edge and vertex, and confirms that every edge in the selected coordinate appears. It also checks the eight-vertex obstruction and its Hamilton certificate. The arbitrary-dimensional proof above is independent of those bounded checks.

When prescribed matching edges use several coordinates, the woven construction may omit them. A local switch to include a missing edge can split the cycle or remove an edge that was already prescribed. We have no invariant that guarantees all such switches preserve a single spanning cycle. Nor does the long-cycle literature result imply that the unvisited vertices can be inserted while retaining the prescribed edges.

Final status.

All matchings in one coordinate direction are covered, and the perfect-matching-completion shortcut has an explicit obstruction. The unrestricted Ruskey--Savage statement is UNRESOLVED by this attempt.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3181 (OPG-600), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Matchings extend to Hamiltonian cycles in hypercubes. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/matchings_extends_to_hamilton_cycles_in_hypercubes.
• S3 J. Fink and T. Mütze, Matchings in hypercubes extend to long cycles, arXiv:2401.01769, revised 2025; precise Ruskey–Savage formulation. https://arxiv.org/abs/2401.01769.