Generating all k-regular graphs by switching edges I want to randomly place $k$ zeroes in each row of a $n \times n$ matrix, such that the resulting matrix is symmetric and no zeroes are on the main diagonal of the matrix.
This problem is equivalent to generating random $k$-regular graphs on n vertices. I have already proven, that this is not possible for odd k and odd n. And I have already found a way to generate a k-regular graph for the other case. I wondered if it is possible to reach every other $k$-regular graph by switching edges. Therefore I want to know if the following can be proven or if there is a counter example.
Let $G$ and $G'$ be $k$-regular graphs on $n$ vertices. Is it possible to change one graph to the other by just switching edges while still having a regular graph after each switch?
(The edges $AB$ and $CD$ get changed to $AC$ and $BD$)
I have already proven that you can switch edges of $G'$ such that a single vertex has the same adjacent vertices as in $G$, but then I haven't found a way to switch the edges in a way that preserves the adjacent vertices of the first m vertices and results in m+1 vertices which having the same adjacent vertices in $G'$ and $G$.
 A: More is true: as long as there is at least one graph with a given degree sequence, all graphs with a given degree sequence are connected by the edge swap operation. You are only interested in the regular case, but that isn't any easier than the general case to prove.
This result is due independently to Havel and Hakimi, but most people are only aware of the Havel–Hakimi algorithm for determining if a sequence is a degree sequence of some graph. That algorithm is the direct corollary of this result.
Suppose two graphs $G$ and $H$ have the same degree sequence: we can label their vertices $v_1, v_2, \dots, v_n$ such that $\deg_G(v_i) = \deg_H(v_i)$ for $i=1,2,\dots,n$. Instead of explaining how to turn $G$ into $H$, I will explain how to turn $G$ and $H$ both into the same graph. Since the operations are reversible, we can get from $G$ to that graph to $H$. Here's how...
Without loss of generality, let's suppose that the vertices are sorted in decreasing order of degree (in both graphs). Then we can:

*

*Perform swaps in both graphs so that $v_1$ is adjacent to $v_2, v_3, \dots, v_{d+1}$ in both graphs, where $d = \deg_G(v_1) = \deg_H(v_1)$.

*Use this algorithm to perform swaps on $G - v_1$ and $H - v_1$ to turn them both into the same graph. This will have the effect of turning $G$ and $H$ into the same graph. We might need to reorder the vertices when we do this, so that the degrees of $v_2, \dots, v_n$ in $G-v_1$ and $H-v_1$ are again in descending order.

Of course, we need to prove that step 1 is always possible.
Suppose that in one of the graphs ($G$, without loss of generality) $v_1$ is not yet adjacent to some vertex $v_i \in \{v_2, \dots, v_{d+1}\}$. Then it must be adjacent to some vertex $v_j$ not in this set. Vertices are sorted by degree, so $\deg(v_i) \ge \deg(v_j)$.
Vertex $v_i$ has $\deg(v_i)$ neighbors among $\{v_2, v_3, \dots, v_n\}$. Vertex $v_j$ only has $\deg(v_j)-1 < \deg(v_i)$ neighbors in that set, since it is also adjacent to $v_1$. (If $v_i v_j$ is an edge, this contributes $1$ to both degrees, so we can ignore it.) Therefore there is a fourth vertex $v_k$ adjacent to $v_i$ but not $v_j$.
Now perform a swap: replace edges $v_1 v_j$ and $v_i v_k$ by $v_1 v_i$ and $v_j v_k$. This increases the number of neighbors of $v_1$ in the set $\{v_2, \dots, v_{d+1}\}$. If we repeat this operation, we can put $G$ and $H$ both in the form we wanted.
