1

I have to determine a vertex- and edge-connectivity of complete bipartite graph but one edge missing. I don't know how to do this, but this is what I have so far. I think it's completly wrong.

I know that $\kappa(G)\le\lambda(G)\le \delta(G)$. In fully connected bipartite graph $K_{m,n}$, minimal degree is equal to $min(m,n)$. That means, in my graph, minimal degree is equal to $min(m-1,n-1)$. What should I do now? I think that $\lambda(G)=min(m-1,n-1)$ too, because I have to remove $min(m-1,n-1)$ edges to disconnect a vertex with minimal degree... But what about vertex-connectivity?

Speedding
  • 357

1 Answers1

2

Without loss of generality, assume that $m \le n$. And we'd like to show that the vertex-connectivity $\kappa(G) = m-1$, where $G$ is the complete bipartite graph on $m + n$ vertices with one edged, say $(a,b)$, removed.

It is enough to show that removing $m-2$ vertices cannot make $G$ disconnected. Suppose the left and the right partite set are of size $m, n$ respectively. After removing $m-2$ vertices from $G$, we get a complete bipartite graph with at most one edge removed. Suppose the partite sets are $A$ and $B$ of the resulting graph. We also know that $|A|, |B| \ge 2$.

Take any two vertices $u$ from $A$ and $v$ from $B$. As $|A|, |B| \ge 2$, we can find $u'\in A\setminus \{a\}$, and $v'\in B\setminus \{b\}$. Thus $u\sim v'\sim u' \sim v$, and so $A$ and $B$ are connected.

Zilin J.
  • 4,270