0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ What are $X$ and $Y$? What are $V_1$ and $V_2$? Which of these are bipartitions, and of what graphs? $\endgroup$ – Misha Lavrov Dec 20 '17 at 17:31
  • $\begingroup$ @MishaLavrov Sorry, I was using bad notation! $X$,$Y$ are the independent sets of $G$. $\endgroup$ – mandella Dec 20 '17 at 17:37
  • $\begingroup$ 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|$.) $\endgroup$ – Misha Lavrov Dec 20 '17 at 20:23
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.