Starting with a given simple, directed Graph G, I define a two-edge swap as:
- select two edges u->v and x->y such that (u!=x) and (v!=y) and (u!=y) and (x!=v)
- delete the two edges u->v and x->y
- add edges u->y and x->v
Is it guaranteed that I can reach any simple directed graph with the original (in- and out-) degree sequence in some finite number of 2-edge swaps?
If we need some sort of 3-edge swaps, what are they?
Background: I intend to use this as MCMC steps to sample random graphs, but over at the Networkx Developer site, there is a discussion that Theorem 7 of the paper P Erdos et al., "A simple Havel–Hakimi type algorithm to realize graphical degree sequences of directed graphs", Combinatorics 2010 implies that we need 3-edge swaps to sample the whole space.