Maximal Hamiltonicity of realization graphs of degree sequences
Jeffrey S. Baggett
math.CO
Sep 7, 2026 · v1
TL;DR
An induction proving realization graphs of graphical degree sequences are maximally Hamiltonian is formalized in Lean 4 and checked by its kernel.
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.
Problem
Whether the realization graph of a graphical degree sequence (vertices are labeled realizations, edges are single 2-switches) is Hamiltonian has been open since Brualdi and appears as Problem P59 in Mütze's Gray-code survey. The goal is to settle it in the strongest form.
Approach
The proof inducts on the number of ground vertices, cutting the realization graph at a single pivot vertex into fibers and the quotient they lie over. The quotient is identified with the Johnson graph of a shifted family of neighborhoods. A classification determines exactly when such Johnson graphs fail to be Hamilton-connected (the Y-families), and pivots are chosen to dodge these exceptions. The entire argument is formalized in Lean 4 and checked by its kernel, assuming only seven cited results.
Results
The realization graph of every graphical degree sequence is maximally Hamiltonian: Hamilton-laceable when bipartite on more than one vertex, and Hamilton-connected otherwise. This answers Problem P59 and the question recorded as open by Barrus.