The problem is the following: if $ G $ is a connected regular bipartite graph, then the graph obtained from $ G $ by removing any pair of vertices, one from each partite set, has a perfect matching.
I try to apply Hall's theorem. First, let $ X $ and $ Y $ be the partite sets of $ G $, let $ x $ and $ y $ be any two vertices of $ X $ and $ Y $ respectively, and let $ H = G - \{ x \} - \{ y \} $. Let $ S $ be a subset of $ X $. If I can prove that $ |S| \leq |N_H(S)| $ then I'm done by Hall's theorem and symmetry. If $ N_G(S) $ does not contain $ y $ then $ N_H(S) = N_G(S) $ and the result follows. I'm having trouble with the case where $ N_G(S) $ contains $ y $. Then $ |N_H(S)| = |N_G(S)| - 1 $ and the inequality may not hold anymore. I try to involve $ x $ into it as well as the connectedness condition but I haven't had any success so far. Please help, thank you.
You should begin by showing that that in a $k$-regular bipartite graph, if $|N(S)| = |S|$ exactly, then the vertices $S \cup N(S)$ induce a connected component of the graph.
Once you've done that, the rest is easy. $G$ is connected, and this means that there is only one set $S \subseteq X$ for which $|N(S)| = |S|$: $S$ must be all of $X$. This set continues to satisfy Hall's condition after $y$ is deleted, because $x$ is deleted as well.
For all other sets, we must have $|N(S)| \ge |S|+1$ in the original graph, which gives us the slack needed to make sure that Hall's condition holds even once $y$ is deleted.