Prove that a $k$-regular bipartite graph with $k \geq 2$ has no cut-edge

Question

Although this seems rather obvious, I couldn't prove it rigorously. Any ideas how to prove it? The graph is assumed to be simple and connected.

Explanation of the terms:

• $k$-regular means that all vertices have degree $k$;
• bipartite means that there are 2 sets of vertices $X, Y$, where vertices from $X$ only have edges with vertices $Y$ and vertices from $Y$ only have edges with vertices from $X$;
• cut-edge is an edge which removal disconnects the graph;

This is b) part of the exercise, maybe a) part can help:

a) If all vertices $v \in G$ have an even degree, $G$ does not have cut-edge

From a) it actually follows that for even $k$, b) is true, thus only case with odd $k$ left to prove.

Answer 1

Ok, here is a simple proof I came up by myself. I was apparently going the wrong way in trying to prove the exercise.

Proof. Suppose edge $e$ is a cut-edge. Study graph $G-e$. For any $v \in G-e$ other then $e$ endpoints $x, y$, the vertex degree $d(v) = k$, and $d(x)=d(y)=k-1$.

Now, since graph $G$ is bipartite, graph $G-e$ remains bipartite. Also, because $e$ is a cut-edge, $G-e$ is composed of 2 components $H_1, H_2$, which are also both bipartite, and each contains exactly one of $x, y$. Assume WLG that $H_1$ has vertex $x$, that $H_1$ has vertex bipartition $X_1, Y_1$ and that $x \in X_1$.

Clearly, in subgraph $H_1$, we have

$S_1 = \sum_{v\in X_1 }d(v) = k(|X_1|-1) + k-1$ and $S_2 = \sum_{v\in Y_1 }d(v) = k(|Y_1|)$, and $S_1$ can't be equal $S_2$ unless $k=1$. However, it must be the case that $S_1 = S_2$ in a bipartite graph. Thus, our initial assumption that $e$ is a cut-edge was wrong. Therefore, $G$ has no cut-edge. $\Box$