Let $G$ be a $k$-regular bipartite graph, and let $G$ contain a bridge. Prove that $k=1$.

Let $G$ be a $k$-regular bipartite graph, and let $G$ contain a bridge. Prove that $k=1$.

I have tried to remove the bridge and find a contradiction that an component should not be bipartite, but I failed.

• Hint: consider edge counts – Bob Krueger Nov 26 '17 at 15:56

Suppose that the removal of the bridge in a $k$-regular graph results in a component of a graph. This component is either a single vertex, in which case the problem is solved or it must be a bipartite graph with vertex partition sets say $V$ and $W$. WLOG, assume that one of the vertices of the bridge was a vertex in $V$. Then because the sum of the degrees of vertices in each partition sets $V$ and $W$ must be equal in a bipartite graph, so $$|W|k=(|V|-1)k+(k-1)\Longrightarrow (|V|-|W|)k=1.$$ Since all quantities are integers, so $k=1$.