This proof shows every matching in hypercubes can extend to cycles visiting a significant fraction of vertices, suggesting broader implications for graph theory.
.The \(d\)-dimensional hypercube graph \(Q_d\) has as vertices all subsets of \(\{1,… ,d\}\), and an edge between any two sets that differ in a single element. The Ruskey–Savage conjecture asserts that every matching of \(Q_d\), \(d≥ 2\), can be extended to a Hamilton cycle, i.e., to a cycle that visits every vertex exactly once. We prove that every matching of \(Q_d\), \(d≥ 2\), can be extended to a cycle that visits at least a \(2/3\)-fraction of all vertices.KeywordshypercubecyclematchingMSC codes05C3805C7005C45
No takes yet. Share an insight, caveat, or question.
Fink et al. (2025) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: