Matchings extend to Hamiltonian cycles in hypercubes

Status partial high confidence

The Ruskey–Savage conjecture that every matching of $Q_d$ ($d \geq 2$) extends to a Hamiltonian cycle remains open. Substantial progress has been made: Fink and Mütze (2025) proved that every matching of $Q_d$ can be extended to a cycle visiting at least $2/3$ of all vertices; Fink and Hotmar (2025) proved the full conjecture for matchings whose edges span at most 5 directions, which in particular settles the $d = 5$ case completely.

Cited literature (4)

• partial Prescribed matchings extend to Hamiltonian cycles in hypercubes with faulty edges (2013)
  Fan Wang, Heping Zhang · arXiv preprint · arXiv:1301.2931

  Every matching of at most $2n-1$ edges in $Q_n$ ($n \geq 2$) can be extended to a Hamiltonian cycle, even in the presence of up to $n-1-\lceil|M|/2\rceil$ faulty edges.

• partial Matchings of quadratic size extend to long cycles in hypercubes (2016)
  Tomáš Dvořák · Discrete Mathematics & Theoretical Computer Science · arXiv:1511.06568

  Every matching in $Q_n$ of size at most $n^2/12 + n/4 + 1/2$ can be extended to a cycle covering at least $3/4$ of all vertices.

• partial Matchings in hypercubes extend to long cycles (2025)
  Jiří Fink, Torsten Mütze · SIAM Journal on Discrete Mathematics · arXiv:2401.01769 · doi:10.1137/24M1670093

  Every matching of $Q_d$ ($d \geq 2$) can be extended to a cycle that visits at least a $2/3$-fraction of all vertices.

• partial Matchings with five directions in hypercubes extend to Hamilton cycles and paths with prescribed ends (2025)
  Jiří Fink, Vojtěch Hotmar · International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2025) · arXiv:2501.19029

  Every matching of $Q_n$ whose edges span at most 5 directions extends to a Hamiltonian cycle (and path with prescribed ends); this settles the conjecture completely for $Q_5$.

Reviewer notes. Fink also proved in 2019 (Combinatorica 39:77–84) that every matching in a hypercube extends into a 2-factor (spanning union of cycles), which is weaker than a single Hamiltonian cycle but provides structural insight. The Q_5 case follows from the 5-directions result of Fink–Hotmar because every matching in Q_5 uses edges in at most 5 directions. The conjecture for general Q_d (d ≥ 6) with matchings spanning more than 5 directions remains open.

Auto-reviewed 2026-05-08 with claude-sonnet-4-6 (worker 05) (web search enabled).