# Reaching all possible simple directed graphs with a given degree sequence with 2-edge swaps

Starting with a given simple, directed Graph G, I define a two-edge swap as:

1. select two edges u->v and x->y such that (u!=x) and (v!=y) and (u!=y) and (x!=v)
2. delete the two edges u->v and x->y
3. 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.

-

On page 6 of the linked paper, a triple swap is defined. Basically, you transform $v_n \rightarrow v_k \rightarrow v_i \rightarrow v_m$ into $v_n \rightarrow v_i \rightarrow v_k \rightarrow v_m$.