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

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.

• What did you try? Where did you get stuck? – David Richerby Oct 29 '13 at 10:57
• Yes, the graph is connected. I was considering several ways of prooving, I can sketch one of them. Delete an edge $e$, remember its endpoints $x, y$. If $e$ was cut-edge, then in $G-e$ there is no path between $x, y$. Suppose $x$ is connected with vertices from set $X_1$, $y$ from set $Y_1$. Sets $X_1$ and $Y_1$ can't have common edges, as otherwise we have a path between $x$ and $y$. However, set $X_1$ must have neighs other then $x$ (since $k$>1), label this set $X_2$. The problem is that $X_2$ is of uncertain size. I can show that $X_3$ has at least one element, but furhter I am stuck. – MindaugasK Oct 29 '13 at 13:13
• Another way of prooving the exercise would be to show that $k$-regular bipartite graph has $2$-regular bipartite graph as a subraph or $k-1$-regular bipartite graph as a subgraph, but I could not come up with an algorithm to delete edges properly (I am nearly sure the algorithm I was thinking about should actually work, but I can't see more than 3-4 steps (edge deletions) ahead) – MindaugasK Oct 29 '13 at 13:22

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$