Skip to main content
2 of 2
added 59 characters in body; edited tags
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Connectivity and the minimum degree of bipartite graph

I want to find a condition on $\delta(G)$ (ex. $\delta(G) \geq an$) that guarantees $\kappa(G)=\delta(G)$ where $\kappa(G)$ is the vertex-connectivity of a bipartite graph $G$, and $\delta(G)$ is the minimum degree of $G$.

In other words, I want to prove that the statement

If $\delta(G) \geq an$, then $\kappa(G)=\delta(G)$

holds for bipartite graphs.

I know that $\delta(G) \geq \frac{n+1}{4}$ implies $\kappa'(G)=\delta(G)$ where $\kappa'(G)$ is the edge-connectivity of $G$, and it is sharp.
Also, I proved that bipartite $G$ is connected if $\delta(G) \geq \frac{n+1}{4}$.
But I have no idea with the vertex-connectivity.
Here are my ideas to find such boundary $an$:

  1. (Contrapositive) Prove the statement "If $\kappa(G)<\delta(G)$, then $\delta(G)<an$."
  2. Use the statement $\delta(G) \geq \frac{n+1}{4}\Rightarrow \kappa'(G)=\delta(G)$. Find the boundary of $\delta(G)$ that implies $\kappa(G)=\kappa'(G)$, and then show this boundary also satisfies $\delta(G) \geq \frac{n+1}{4}$.

Would you help me?

okw1124
  • 341
  • 1
  • 9