The realization graph of every degree sequence has a Hamilton path

Abstract

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).

Disclosure

“btain a Hamilton path in GF (d). Otherwise, observe that the only realization of G(d) is the complete or empty graph, and thus there trivially exists a Hamilton path in GF (d). Acknowledgment The authors acknowledge the use of large language models for assistance in improving the clarity, grammar, and overall readability of the English text. All technical content, ideas, results, and conclusions presented in this work are the original contributions of the authors. A preliminary v”

PDF page 12

Classification

Proofreading, grammar, or spelling

Multiplier

1

Verified

2026-08-23T18:58:52.067782Z

Structural counts