The realization graph of every degree sequence has a Hamilton path

Abstract

For a degree sequence $d$, the realization graph ${\mathcal{G}}_{\mathcal{F}}(d)$ is the graph whose vertices are the labeled realizations of $d$, two of which are adjacent if they differ by a single $2$-switch. We prove that for every degree sequence $d$ and every realization $S$ of $d$, the graph ${\mathcal{G}}_{\mathcal{F}}(d)$ contains a Hamilton path starting at $S$. This answers a question of Barrus (2016), which was also raised independently by Mütze (2023) in his survey of combinatorial Gray codes. As a consequence, an embedding observation of Arikati and Peled (1999) implies that for any vectors $R$ and $C$ of non-negative integers, the interchange graph ${\mathcal{A}}_{\mathcal{F}}(R,C)$ of $(0,1)$-matrices with row sums $R$ and column sums $C$ contains a Hamilton path starting at any prescribed matrix, thereby resolving a question of Brualdi (1980).

arXiv comment17 pages, 6 figures