# 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!

• Is there some hypothesis on $k$. What about the graph with 2 vertices and 1 edge? – Sigur Jul 27 '12 at 13:24
• @Sigur That one is 2-connected. – Weltschmerz Jul 27 '12 at 13:29

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.

• I'm not sure about the last equality. Why is it so? It seems that in the inequality you're considering degrees in $G-v$, but in the equality, degrees in $G$. – Weltschmerz Jul 28 '12 at 22:55
• The vertex sets $L$ and $R$ form a connected component after the removal of $v$, and of course this component is still bipartite. So all the edges of $L$-vertices have their endpoint within the connected component, but outside of $L$, so they must end in $R$ and vice versa. Thus every edge in $G[L\cup R]$ has an endpoint in $L$ and an endpoint $R$, so the degree on one side is the same as the other. – Luke Mathieson Jul 29 '12 at 0:20
• Why $\exists G_b$ such that $|V_1\cap V(G_b)|\ge|V_2\cap V(G_b)$? – JoseA132 Jun 5 '17 at 2:22

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: 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.

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,$$ a contradiction.