A connected k-regular bipartite graph is 2-connected.

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!

Solutions Collecting From Web of "A connected k-regular bipartite graph is 2-connected."

Let $G = (V_{1}\cup V_{2},E)$ be a connected, $k$-regular bipartite graph where $V_{1}$ and $V_{2}$ are the partite vertex sets. As the case $k=1$ is trivial, we may assume that $k \geq 2$ and therefore $|V_{1}\cup V_{2}|\geq 4$.

Assume for contradiction that $G$ is not $2$-connected.

As $G$ is connected but not $2$-connected, there exists a vertex $v$ whose removal disconnects the graph. Without loss of generality we may assume that $v \in V_{1}$. Then $G-v = \uplus_{i\in [1,a]} G_{i}$ where each $G_{i}$ is a connected component and $a \geq 2$.

As $a \geq 2$, there exists some component $G_{b}$ such that $|V_{1}\cap V(G_{b})| \geq |V_{2}\cap V(G_{b})|$. (It shouldn’t be too hard to convince yourself of this) For convenience denote $L = V_{1}\cap V(G_{b})$ and $R = V_{2}\cap V(G_{b})$.

As $G_{b}$ is a connected component and $G$ was connected, and $v \in V_{1}$, at least one vertex in $R$ was adjacent to $v$, and therefore has degree less than $k$. However the vertices in $L$ have lost no edges Then we have
$$\sum_{u\in R}deg(u) < k\cdot|R| < k\cdot|L| = \sum_{w \in L}deg(w)$$
However as $G[L \cup R]$ forms a bipartite graph, we know
$$\sum_{u\in R}deg(u) = \sum_{w \in L}deg(w)$$

Thus we have a contradiction, so $G$ must be at least $2$-connected.

Proof by contradiction. Suppose $v$ is a cut vertex of $G = G(X,Y).$ Without loss of generality, let $v\in Y.$ Then $G-v$ has at least two components, say $C_1$ and $C_2.$ Let $(X_1,X_2)$ be the bipartition of $C_1.$ Let $s$ be the number of neighbors of the vertex $v$ in $C_1$ (that is, in $X_1$), then $s<r.$

Since $C_1$ is bipartite, the number of edges incident at $Y_1$ in $C_1$ must be equal to the number of edges incident at $X_1$ in $C_1.$ Hence
$$r|Y_1| = s(r-1) + (|X_1| – s)r$$
$$\Rightarrow s = (|X_1| – |Y_1|)r$$
$$\Rightarrow s \geq r,$$