Demostrar que todo grafo bipartito k-regular con al menos 3 vértices es 2-conectado para k al menos 2

Question

He visto la respuesta a esta pregunta aquí: Un grafo bipartito k-regular conectado es 2-conectado. Pero yo tenía un enfoque ligeramente diferente, pero no estoy seguro de que sea correcto. Dejemos que $G= X \cup Y$ como en el supuesto, y proceder por contradicción que no es 2-conectado. Entonces tiene un vértice de corte digamos $v$ y $G-v$ tiene componentes $G_1,...G_i$ donde $i\geq 2$ . Ahora existe algún componente tal que: $L=|XV(Gb)||YV(Gb)|=R $ y ahora mi enfoque:

Dejemos que $S$ sea el conjunto de aristas con exactamente un extremo en $V(G_b)$ . Entonces cada arista en $S$ tiene un extremo en $R$ y así $$k|R|=\sum_{v \in R} deg(v) = |S|+e(G_b) > e(G_B) =\sum_{v \in L} deg(v)=k|L|$$ y esto es una contradicción. ¿Funciona esto?

Answer 1

Su argumento es válido, siempre que supongamos (sin pérdida de generalidad) que $v \in X$ . Entonces $S$ es sólo el conjunto de aristas de $v$ a $G_b$ cuyo extremo "izquierdo" es $v$ y cuyo extremo "derecho" es un vértice de $R = V(G_b) \cap Y$ .

Entonces es cierto que $k|L| = |E(G_b)|$ (ya que ninguno de los vértices de $L$ puede ser adyacente a $v$ ) y $k|R| = |E(G_b)| + |S| > k|L|$ Así que $|R| > |L|$ .

Esto significa que $|R| \ge |L|+1$ sumando todos los componentes, obtenemos $|Y| \ge (|X|-1)+i$ ya que dejamos fuera $v$ de $X$ y ver todos los vértices de $Y$ . Pero debemos tener $|X| = |Y|$ ya que $k|X|=|E(G)|=k|Y|$ Así que $i \le 1$ .

(O podemos invertir este argumento, asumiendo que $i \ge 2$ y demostrar la existencia de un componente $G_b$ donde $|R| \le |L|$ . Esto es lo que supongo que estás haciendo, aunque no explicas cómo has encontrado este componente).