bipartite-graphsgraph theorygraph-connectivity
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.
Let $G$ be a graph and let $\kappa(G)$ be the size of any minimum vertex separating set of $G$, $\lambda(G)$ be the minimum size of any edge separating set of $G$, and let $\delta(G)$ be the minimum degree of $G$. It is well known that $$\kappa(G)\le\lambda(G)\le\delta(G).$$ Since $\delta(G)=2$ and $G$ is connected then $\kappa(G)=1\text{ or }2$. Can you show that $\kappa(G)\ne 1$?
When you are drawing graphs, edges should never meet unless they are crossing or share a vertex in common and they should only meet in those locations. The way you have drawn your graph seems to indicate that $\deg(v_5)=3$ when it is really true that $\deg(v_5)=4$. Similarly for $v_7$.
Would separating $A$ into two nodes connected by one edge work? Also, the minimum degree of your graph is $2$ at each of the four corner nodes.
The graph with the largest minimum degree, lowest edge connectivity, and lowest vertex connectivity is formed by connecting two complete graphs with one singular edge like a bridge.
Best Answer
Let $n$ be any positive integer. Induction over $m$.
$m=1$: $K_{1,n}$ is the star, which is connected, so $\lambda(K_{1,n})\geq 1$. But we can remove any single edge to get an isolated vertex, so $\lambda(K_{1,n}) = 1$.
$m\mapsto m+1$: Regard $H\cong K_{m,n}$ as a specific subgraph of $K_{m+1,n}$. Denote the vertices in the partition of $K_{m+1,n}$ by $v_1,\ldots,v_{m+1}$ and $u_1,\ldots,u_n$ respectively. Let $E$ be an edge-cut of $K_{m+1,n}$, then $E\cap E(H)$ is an edge-cut of $H$.
First case: $n\leq m$. By induction thesis $|E\cap E(H)|\geq n$ and so $|E|\geq n$. Since we can specify an edge-cut of size $n$ we have $\lambda(K_{m+1,n})=n$.
Second case: $n>m$. Parallel to the first case, we have $|E\cap E(H)|\geq m$ and so $|E|\geq m$. If one of the edges incident with the new vertex $v_{m+1}$ was in $E$ (but because of the incidence not in $E(H)$), we would have $|E|\geq m+1$. On the other hand assume that none of the edges incident with $v_{m+1}$ is in $E$, so all of $u_1,\ldots,u_n$ are adjacent to $v_{m+1}$. Since $E$ is edge-cut, there must be a vertex in $\{v_1,\ldots,v_m\}$ that isn't adjacent to any of the $u_1,\ldots,u_n$ vertices (else $G\setminus E$ would still be connected). Therefore, at least all $n$ edges in that vertex must be cut and we have $|E|\geq n\geq m+1$, which concludes the proof, since we can specify an edge-cut of size $m+1$.