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.

  • $\begingroup$ Hint: consider edge counts $\endgroup$ – 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$.

  • $\begingroup$ you are welcome! $\endgroup$ – PJK Nov 27 '17 at 2:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.