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

1.1k Views Asked by At

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?

1

There are 1 best solutions below

0
On BEST ANSWER

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