The realization graph of every degree sequence has a Hamilton path

Abstract

Given a degree sequence $d$, the realization graph ${\mathcal{G}}_{\mathcal{F}}(d)$ is the graph whose vertices are all labeled realizations of $d$, where two realizations are adjacent if they differ by a single $2$-switch. We prove that ${\mathcal{G}}_{\mathcal{F}}(d)$ admits a Hamilton path for every degree sequence $d$. The problem was initiated by Arikati and Peled (1999), who showed that ${\mathcal{G}}_{\mathcal{F}}(d)$ contains a Hamilton cycle whenever $d$ has majorization gap of 1. Later, Barrus (2016) and independently Mütze (2023) asked whether a Hamilton path or cycle exists in ${\mathcal{G}}_{\mathcal{F}}(d)$ for every degree sequence $d$. As a consequence, we obtain that the interchange graph of $(0,1)$-matrices with prescribed row and column sums has a Hamilton path, thereby answering a question of Brualdi (1980).

14 pages, 7 figures