First off, let me reformulate the problem. I call edges of $G$ black. Let $K_{k,n}$ be the complete graph on the same partite sets $V_1, V_2$, whose edges I will refer to as red. Let $H$ be the superposition (i.e. gluing of identical vertices) of $G$ and $K_{k,n}$. The graph $H$ is a two-colored graph, where each vertex has as many incident black edges as red ones. Hence, $H$ can be decomposed into a collection of *alternating cycles* (where the color of edges along each cycle alternate between black and red).

The problem is equivalent to finding an alternating cycle decomposition composed of 2- and 4-cycles only. Indeed, one can set up a one-to-one correspondence between pairs of black edges being exchanged in $G$ and 4-cycles (formed by the original two black edges and a pair of red edges corresponding to what the black edges become after the exchange) in $H$, and between black edges staying put in $G$ and 2-cycles (formed by parallel black and red edges) in $H$.

**Theorem.** The graph $H$ has an alternating cycle decomposition into 2- and 4-cycles.

```
The proof below may be incomplete. See comments.
```

**Proof.** Let $D$ be an alternating cycle decomposition of $H$ with the maximum number of 4-cycles. We will show that in $D$ there are no cycles of length $>4$. Assume that such a cycle $c$ exists.

I will call a red edge available if in $D$ it belongs to a cycle of length $\ne 4$.

Consider any triple of consecutive black-red-black edges (*brb-path*) $p$ in $c$. Clearly, its endpoints belong to distinct partite sets in $H$ and thus are connected by a red edge $e$. If $e$ is available, then we can form a new 4-cycle from $p$ and $e$ (and reshuffle the remaining edges from $c$ and the cycle of $e$ into some new cycles) to obtain a new cycle decomposition, where the number of 4-cycles is one more than in $D$. This contradiction to the definition of $D$ implies that $e$ is not available, and thus $e$ belongs to a 4-cycle $q$ in $D$. Let $T_1$ be the superposition of $c$ and $q$, and $b_1$ be any of the black edges of $q$. It is easy to see that $b_1$ is attached to $c$ (at an endpoint of $e$) in $T_1$.

Now, let us consider a brb-path $p_1$ starting at $b_1$ and then going along $c$. Again, its endpoinds are connected by a red edge $e_1$ in $H$. If $e_1$ is available, we can construct two new 4-cycles formed by $p_1$ and $e_1$, and by $p$ and $e$, which will destroy only one 4-cycle $q$. Hence, we'd obtain a cycle decomposition with a larger number of 4-cycles than $D$, a contradiction. It follows that $e_1$ is not available, and thus $e_1$ belongs to a 4-cycle $q_1$ in $D$. Let $T_2$ be the superposition of $T_1$ and $q_1$, and $b_2$ be a black edge of $q_1$ that is attached to $c$ in $T_2$.

Continuing this process we will get an infinite series $(T_k,b_k)$, where the size of $T_k$ grows, which is impossible. The contradiction proves that cycle $c$ does not exist, and thus all cycles in $D$ have length $2$ or $4$. QED

4more comments