Maximal Hamiltonicity of realization graphs of degree sequences
Abstract
We prove that the realization graph of every graphical degree sequence is maximally Hamiltonian: it is Hamilton-laceable when bipartite on more than one vertex, and Hamilton-connected otherwise. This answers Problem P59 of Mütze's survey of combinatorial Gray codes, and the Hamiltonicity question recorded as open by Barrus, in the strongest form either admits. The argument is an induction on the number of ground vertices, cutting the realization graph at a single ground vertex into fibers and the quotient they lie over. The proof is formalized in Lean 4 and checked by its kernel, with seven results cited from the literature and nothing else assumed. Its engine is a classification. The realizable neighborhoods of a ground vertex form a shifted family -- one closed under replacing an element by a smaller one -- and the quotient is the Johnson graph of that family. Such a Johnson graph can fail to be Hamilton-connected, and we determine exactly when: the failures are one explicit family of examples, the Y-families, and each of them fails between a single pair of its members. A shifted family with a greatest member never fails, and those families are exactly the shifted matroids, where the conclusion already follows from the theorem of Naddef and Pulleyblank on the graphs of 0/1-polytopes. The obstruction lives entirely outside the matroid case, which is why it has not been met before.
Related
- Degree sequences of spectrally extremal connected nonregular graphs with prescribed maximum degree: the dense case
- Total eight-colorings of maximal planar graphs of maximum degree six
- Quasimonophobic graphs and degree spectral sequences in discrete cubical homology
- Hamiltonicity in graphs defined by primes and primitive elements
- On the Hamiltonicity of generating graphs of almost simple groups
BibTeX
@misc{baggett2026maximal,
title = {{Maximal Hamiltonicity of realization graphs of degree sequences}},
author = {Jeffrey S. Baggett},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.08007},
eprint = {2609.08007},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.08007},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Maximal Hamiltonicity of realization graphs of degree sequences
AU - Jeffrey S. Baggett
PY - 2026
DA - 2026/09/07
PB - arXiv
DO - 10.48550/arxiv.2609.08007
UR - https://arxiv.org/abs/2609.08007
AB - We prove that the realization graph of every graphical degree sequence is maximally Hamiltonian: it is Hamilton-laceable when bipartite on more than one vertex, and Hamilton-connected otherwise. This answers Problem P59 of Mütze's survey of combinatorial Gray codes, and the Hamiltonicity question recorded as open by Barrus, in the strongest form either admits. The argument is an induction on the number of ground vertices, cutting the realization graph at a single ground vertex into fibers and the quotient they lie over. The proof is formalized in Lean 4 and checked by its kernel, with seven results cited from the literature and nothing else assumed. Its engine is a classification. The realizable neighborhoods of a ground vertex form a shifted family -- one closed under replacing an element by a smaller one -- and the quotient is the Johnson graph of that family. Such a Johnson graph can fail to be Hamilton-connected, and we determine exactly when: the failures are one explicit family of examples, the Y-families, and each of them fails between a single pair of its members. A shifted family with a greatest member never fails, and those families are exactly the shifted matroids, where the conclusion already follows from the theorem of Naddef and Pulleyblank on the graphs of 0/1-polytopes. The obstruction lives entirely outside the matroid case, which is why it has not been met before.
ER -