# Prove that every connected k-regular bipartite graph on at least 3 vertices is 2-connected for k at least 2

I have seen this question answered here:A connected k-regular bipartite graph is 2-connected. , but I had a slightly different approach, but I am not sure if it is correct. Let $G= X \cup Y$ as in the assumption, and proceed by contradiction that it is not 2-connected. Then it has a cut-vertex say $v$, and $G-v$ has components $G_1,...G_i$ where $i\geq 2$. Now there exists some component such that: $L=|X∩V(Gb)|≥|Y∩V(Gb)|=R$ and now my approach:

Let $S$ be the set of edges with exactly one end in $V(G_b)$. Then every edge in $S$ has one end in $R$ and so $$k|R|=\sum_{v \in R} deg(v) = |S|+e(G_b) > e(G_B) =\sum_{v \in L} deg(v)=k|L|$$ and this is a contradiction. Does this work?

• What are $X$ and $Y$? What are $V_1$ and $V_2$? Which of these are bipartitions, and of what graphs? – Misha Lavrov Dec 20 '17 at 17:31
• @MishaLavrov Sorry, I was using bad notation! $X$,$Y$ are the independent sets of $G$. – mandella Dec 20 '17 at 17:37
• Makes sense now. (Though I have one more objection to your notation: you don't want $L = |X \cap V(G_b)| \ge |Y \cap V(G_b)| = R$, which implies $L$ and $R$ are numbers, but $L := X \cap V(G_b)$, $R := Y \cap V(G_b)$, and $|L| \ge |R|$.) – Misha Lavrov Dec 20 '17 at 20:23

Your argument is valid, provided we assume (without loss of generality) that $v \in X$. Then $S$ is just the set of edges from $v$ to $G_b$, whose "left" endpoint is $v$ and whose "right" endpoint is a vertex of $R = V(G_b) \cap Y$.
Then it's true that $k|L| = |E(G_b)|$ (since none of the vertices in $L$ can be adjacent to $v$) and $k|R| = |E(G_b)| + |S| > k|L|$, so $|R| > |L|$.
This means $|R| \ge |L|+1$; adding these up over all components, we get $|Y| \ge (|X|-1)+i$ since we leave out $v$ from $X$, and see all vertices of $Y$. But we must have $|X| = |Y|$, since $k|X|=|E(G)|=k|Y|$, so $i \le 1$.
(Or we can reverse this argument, assuming that $i \ge 2$ and proving the existence of a component $G_b$ where $|R| \le |L|$. This is what I assume you're doing, though you're not spelling out how you found this component.)