Constrained Switching in Graphs: A Constructive Proof

Many real networks exhibit strongly-skewed, heavy-tailed degree distributions, one of the indicators of so-called `complex´ networks, and there is a lot of current research in this area. Much of this research requires the generation of random graphs with the same degree distribution as one another, and it is important that these random graphs should be sampled from the space of all graphs with that degree sequence. In this paper we present a novel constructive proof of an existing theorem that sufficient random degree-preserving rewirings can potentially produce any graphs with a given degree distribution.