2026/07/20 by Petr Hladík, Jiří Fink
#math.CO
Given a degree sequence d, the realization graph GF(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 GF(d) admits a Hamilton path for every degree sequence d. The problem was initiated by Arikati and Peled (1999), who showed that GF(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 GF(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).