Graph Theory – Proving a Connected k-Regular Bipartite Graph is 2-Connected

graph theory

I've been struggling with this exercise; all ideas have been unfruitful, leading to dead ends. It is from Balakrishnan's A Textbook of Graph Theory, in the connectivity chapter:

Prove that a connected k-regular bipartite graph is 2-connected.

(That is, deletion of one vertex alone is not enough to disconnect the graph).

I think the objective is to make use of Whitney's theorem according to which a graph (with at least 3 vertices) is 2-connected iff any two of its vertices are connected by at least two internally disjoint paths. But I'll welcome any ideas or solutions.

Thank you!

Best Answer

If there's a cut-vertex $v$, some neighbor of $v$ induces in $G \setminus \{v\}$ a connected bipartite graph with bipartition $A \cup B$. It looks something like:

enter image description here

We observe:

  • By definition, the number of edges from $A$ to $B$ is $k|V(A)| \equiv 0 \pmod k$.
  • If $b$ is the number of edges from $B$ to $v$, then $b < k$, otherwise $v$ is not a cut vertex (in this case, deleting $v$ gives the connected graph induced by $A \cup B$).
  • By definition, the number of edges from $B$ to $A$ is $k|V(B)|-b \not\equiv 0 \pmod k$, since $k \geq 2$.

This is a contradiction.

Related Question