The realization graph of every degree sequence has a Hamilton path

Given a degree sequence $d$, the realization graph $\mathcal{G_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_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_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_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).