Consider a $k$-regular, $k\geq 3$, connected bipartite graph $G=(V,E)$. $G$ has a perfect matching $M$ by Hall's theorem. I am wondering whether there is always a perfect matching such that $G'=(V,E\backslash M)$ is connected. I found that this is not necessarily the case. For example consider the cycles on $4$ and $6$ vertices and join them approriately to obtain connected a $3$-regular bipartite graph $\bar{G}$. These new edges form a perfect matching $M$ in $\bar{G}=(V,\bar{E})$ but $(V,\bar{E}\backslash M)$ is disconnected. But starting from $\bar{G}$ I also find perfect matchings which yield the desired property.
I do not see how I can approach this rigorously. I tried arguing ad absurdum that if I were to have only disconnecting perfect matches, than for any $v,w$ and any path $\phi_{v,w}$ between them there was a perfect match $M$ which disconnected $\phi_{v,w}$ when removing the edges in $M$ from $G$. But I do not find a way to go on.
A) Is the statement even true?
B) If so what would be a good approach for a proof?
Best Answer
This is false for $k=3$. If you remove a perfect matching from a $3$-regular graph, the result is a union of cycles; the only way this could be connected is if it's a Hamiltonian cycle. The Horton graph is an example of a $3$-regular bipartite graph that does not have a Hamiltonian cycle. A smaller example can be found here.
If it were true for any $k$, it would also be true for $k+1$ (and then for all higher $k$). Take any $(k+1)$-regular bipartite graph $G$ and remove a perfect matching $M$; suppose $G-M$ has $t$ $k$-regular components $G_1, G_2, \dots, G_t$. Then we can find perfect matchings $M_1', M_2', \dots, M_t'$ inside those that preserve their connectivity. Let $M' = M_1' \cup M_2' \cup \dots \cup M_t'$; then in $G-M'$ we have not disconnected any $G_i$, and those are connected by $M$, so $G-M$ is connected.
Along the same lines, we can prove a partial result: if we have a $k$-regular bipartite graph with $k\ge3$ and at most $k(k-1)$ vertices, it has a perfect matching that preserves connectedness. This is true for $k=3$, since the only $3$-regular bipartite graph with at most $6$ vertices is $K_{3,3}$, in which any matching works.
To induct on $k$, let $G$ be any $k$-regular bipartite graph on at most $k(k-1)$ vertices, and let $M$ be any perfect matching in $G$. If $G-M$ is connected, we're done. Otherwise, every $(k-1)$-regular bipartite graph has at least $2(k-1)$ vertices, and so every component of $G-M$ has at most $k(k-1) - 2(k-1) = (k-1)(k-2)$ vertices. By induction, every component of $G-M$ has a perfect matching that preserves its connectedness, and once again, gluing those together gives us such a matching in $G$.