Graph Theory (Edge connectivity of a complete bipartite graph $K_{m,n}$

Question

Find $\lambda (K_{m,n})$, where both m and n are at least 1.

I think the answer is $\min(m,n)$ (intuitively), but I'm not sure about my answer. (Specifically, I want to prove that this graph is connected after removing less than $\min(m,n)$ edges. Help me,please.

Answer 1

Since the graph is complete bipartite, the vertices will have either m or n as vertex degree. So it is the removal of minimum of (m,n) that makes the graph disconnected.

Answer 2

You could also use this:

The vertex-connectivity of a graph is less than or equal to its edge-connectivity. That is, κ(G) ≤ λ(G).. (Source: https://en.wikipedia.org/wiki/Connectivity_(graph_theory)#Bounds_on_connectivity)

As noted, $\lambda(K_{m,n}) \leq \min(m,n)$ since each vertex has degree $m$ or $n$. To show that $\lambda(K_{m,n}) \geq \min(m,n)$, the above result implies that it suffices to show $\kappa(K_{m,n}) \geq \min(m,n)$. Let $X$ be the part with $m$ vertices and $Y$ the part with $n$ vertices. The subgraph of $K_{m,n}$ induced by any $m'$ vertices of $X$ and $n'$ vertices of $Y$ is clearly $K_{m',n'}$, which is connected if $m', n'\geq 1$. Hence, in order to disconnect $K_{m,n}$ by removing vertices, we must remove either all of $X$ or all of $Y$, so $\kappa(K_{m,n}) \geq \min(|X|,|Y|) = \min(m,n)$.