Toughness Of Complete Bipartite Graphs

Vertex Deletions and Toughness

A graph may be connected before any vertices are removed, yet become fragmented when a small set of vertices is deleted. Toughness records the smallest ratio between the size of such a deletion set and the number of components it creates. Complete bipartite graphs provide a setting where this quantity can be calculated exactly: their edges make every remaining vertex on one side adjacent to every remaining vertex on the other.

Throughout, graphs are finite and simple. Let $G=(V,E)$, and let $c(H)$ denote the number of connected components of a graph $H$, with $c(H)=0$ when $H$ has no vertices. For $S\subseteq V$, $G-S$ is the graph obtained by deleting the vertices in $S$ and all incident edges. A set $S$ is eligible in the definition below only if $G-S$ has more than one component.

Definition: For a connected graph $G$ with at least one vertex set $S$ such that $c(G-S)>1$, its toughness is $$ t(G)=\min_{\substack{S\subseteq V(G)\\c(G-S)>1}}\frac{|S|}{c(G-S)}. $$ The condition $c(G-S)>1$ excludes deletions that leave a connected graph or no graph at all. A graph with no eligible set is conventionally assigned infinite toughness; that convention will not be needed for the complete bipartite graphs considered here.

Write $K_{m,n}$ for the complete bipartite graph with disjoint parts $A$ and $B$, where $|A|=m$, $|B|=n$, every vertex of $A$ is adjacent to every vertex of $B$, and there are no edges within either part. We assume $m,n\geq 1$ and $m+n\geq 3$. These assumptions ensure that the graph is connected and that at least one eligible deletion exists.

Which Deletions Create Multiple Components?

Consider an arbitrary vertex set $S\subseteq V(K_{m,n})$. Let $a$ be the number of vertices of $A$ not deleted and $b$ the number of vertices of $B$ not deleted. The remaining graph is $K_{a,b}$, allowing $a=0$ or $b=0$. If $a>0$ and $b>0$, the remaining graph is connected: any vertex in $A$ is adjacent to every vertex in $B$, and two vertices on the same side are joined by a path of length two through the other side. Thus this case has $c(G-S)=1$ and is not eligible.

If $a=0$, the remaining graph consists of $b$ isolated vertices, so $c(G-S)=b$. It is eligible exactly when $b\geq 2$. In that case all of $A$ has been deleted, $|S|\geq m$, and equality $|S|=m$ is achieved by deleting $A$ and no vertices of $B$. If $b=0$, the remaining graph consists of $a$ isolated vertices, and it is eligible exactly when $a\geq 2$. The smallest deletion set in this case is all of $B$, of size $n$.

Key observation: Every eligible deletion removes all of at least one part and leaves at least two vertices in the other part. For a fixed remaining side, deleting any additional vertices cannot improve the ratio: it increases $|S|$ and does not increase the number of remaining isolated vertices.

This classification reduces the minimization to at most two ratios. Deleting all of $A$ is a candidate only if $n\geq 2$, and its ratio is $m/n$. Deleting all of $B$ is a candidate only if $m\geq 2$, and its ratio is $n/m$. When both parts have size at least two, both candidates occur. If one part has size one, only the deletion of that singleton part can leave at least two vertices on the other side.

The Toughness Formula

Theorem: For positive integers $m,n$ with $m+n\geq 3$, $$ t(K_{m,n})=\frac{\min(m,n)}{\max(m,n)}. $$

Proof. Let the two parts be $A,B$, with sizes $m,n$. By the classification, if an eligible $S$ leaves vertices from both parts, then it has one component and is not included in the minimum. Hence an eligible $S$ leaves vertices from exactly one part. Suppose it leaves $b\geq 2$ vertices of $B$ and no vertices of $A$. Then $c(G-S)=b$, $|S|\geq m$, and $b\leq n$, so $$ \frac{|S|}{c(G-S)}\geq\frac{m}{b}\geq\frac{m}{n}. $$ Equality is attained by $S=A$, so this deletion type has minimum ratio $m/n$ whenever $n\geq2$. In the other case, $S$ leaves $a\geq2$ vertices of $A$ and no vertices of $B$. Then $c(G-S)=a$, $|S|\geq n$, and $a\leq m$, giving $|S|/c(G-S)\geq n/a\geq n/m$. Equality is attained by $S=B$, whenever $m\geq2$. If $m,n\geq2$, the overall minimum is $\min(m/n,n/m)=\min(m,n)/\max(m,n)$. If $m=1$, then $n\geq2$; only the first deletion type is eligible, and its ratio is $1/n=\min(m,n)/\max(m,n)$. If $n=1$, then $m\geq2$; only the second type is eligible, and its ratio is $1/m=\min(m,n)/\max(m,n)$. These cases exhaust the positive $m,n$ with $m+n\geq3$. $\square$

Worked Calculations

Worked Example: Unequal Parts of Sizes Two and Five

Let $G=K_{2,5}$, with $A=\{a_1,a_2\}$, $B=\{b_1,b_2,b_3,b_4,b_5\}$, and $E=\{a_i b_j: i\in\{1,2\},\,j\in\{1,2,3,4,5\}\}$. The graph has seven vertices and ten edges. Find its toughness by checking the eligible deletion types.

First delete all of $A$. The remaining five vertices $b_1,\ldots,b_5$ are isolated, so $c(G-A)=5$, while $|A|=2$. Substitution gives $$ \frac{|A|}{c(G-A)}=\frac{2}{5}=0.4. $$ Next delete all of $B$. The two remaining vertices $a_1,a_2$ are isolated, so $c(G-B)=2$, while $|B|=5$. This ratio is $$ \frac{|B|}{c(G-B)}=\frac{5}{2}=2.5. $$ Both deletions are eligible. Every eligible deletion must be of one of these types, or delete extra vertices from the side that remains; those extra deletions cannot lower the ratio. Therefore the minimum is $2/5$.

Check: The theorem gives $\min(2,5)/\max(2,5)=2/5$, agreeing with the deletion calculation. The larger ratio $5/2$ from deleting $B$ is real, but it does not determine the minimum.

Worked Example: A Complete Bipartite Star

Let $G=K_{1,4}$, with $A=\{x\}$, $B=\{y_1,y_2,y_3,y_4\}$, and $E=\{xy_1,xy_2,xy_3,xy_4\}$. Deleting $A$ leaves four isolated vertices, so $|A|=1$, $c(G-A)=4$, and the ratio is $1/4=0.25$.

It is important to check the other side as well. Deleting all of $B$ leaves just $x$, which has one component, not more than one. Thus this deletion is not eligible. More generally, if any vertices of $B$ remain along with $x$, the remaining graph is connected; if none remain, only $x$ is left. Hence the deletion of $A$ is the only eligible type, and $t(K_{1,4})=1/4$.

Check: Substitution into the formula gives $\min(1,4)/\max(1,4)=1/4$, the same value. The graph has five vertices and four edges, matching its stated vertex and edge sets.

Worked Example: Equal Parts of Size Three

Let $G=K_{3,3}$, with $A=\{a_1,a_2,a_3\}$, $B=\{b_1,b_2,b_3\}$, and $E=\{a_i b_j: i,j\in\{1,2,3\}\}$. Deleting $A$ leaves three isolated vertices, giving $|A|/c(G-A)=3/3=1$. Deleting $B$ also leaves three isolated vertices, giving $|B|/c(G-B)=3/3=1$.

If a deletion leaves at least one vertex from each part, the remaining complete bipartite graph is connected and is ineligible. If it leaves vertices from only one part and has more than one component, it must have deleted the opposite part; deleting additional vertices from the remaining part makes the numerator larger and the component count smaller. Such a deletion cannot improve on the ratio $1$. Therefore $t(K_{3,3})=1$.

Check: The formula gives $\min(3,3)/\max(3,3)=3/3=1$. There are nine edges, since each of the three vertices in $A$ is adjacent to all three vertices in $B$; this independently agrees with the specified edge set.

Comparison with the Hamiltonian Toughness Bound

A graph is Hamiltonian if it contains a cycle that visits every vertex exactly once. The necessary toughness bound for Hamiltonian graphs is that their toughness is at least $1$. Here is a direct justification of the bound. If $G$ is Hamiltonian, fix a Hamiltonian cycle and let $S\subseteq V(G)$ satisfy $c(G-S)>1$. Since $G$ is connected, $S$ cannot be empty. Removing $|S|$ vertices from the cycle leaves at most $|S|$ consecutive runs of vertices: each run begins immediately after a deleted vertex as the cycle is traversed. Each nonempty run is connected along the cycle, so it lies in one component of $G-S$. Every component of $G-S$ contains at least one such run: a component has a vertex, and that vertex belongs to a run. Different components cannot contain the same run. Consequently $c(G-S)\leq |S|$, and $|S|/c(G-S)\geq1$. This holds for every eligible $S$, so $t(G)\geq1$.

For $K_{m,n}$, the formula shows that $t(K_{m,n})<1$ exactly when $m\ne n$. Indeed, if $m\ne n$, then $\min(m,n)<\max(m,n)$, so their ratio is less than $1$. If $m=n$, the ratio is $1$. Thus every complete bipartite graph with unequal part sizes fails the necessary toughness bound and cannot be Hamiltonian. Equal part sizes pass this particular necessary test; passing it alone does not establish Hamiltonicity.

Conclusion: For positive $m,n$ with $m+n\geq3$, the toughness is the smaller part size divided by the larger part size. The Hamiltonian toughness bound rules out exactly the unequal-part cases among these complete bipartite graphs.

Common Pitfall

A frequent error is to overlook that deleting an entire part can leave several isolated vertices, even though there are no edges in the remaining part. For $K_{2,5}$, an incorrect calculation might say: “Deleting all five vertices of $B$ leaves only two vertices of $A$, so the deletion cannot leave more than one component.” This confuses the number of remaining vertices with the number of components. Since $A$ has no internal edges, the two remaining vertices are isolated from each other. Thus $c(G-B)=2$, and the eligible ratio is $5/2$.

The correction does not change the minimum: deleting $A$ leaves five isolated vertices and gives $2/5$, while $5/2>2/5$. Both eligible directions must be checked when both part sizes are at least two, and the toughness is the smaller of the resulting ratios—not whichever deletion happens to be considered first.

Check Your Understanding

For each question, remember that eligibility requires strictly more than one component after deletion.

For $K_{3,7}$, what are the ratios obtained by deleting each whole part, and what is the toughness?
In $K_{1,6}$, is deleting the part of size six eligible? Explain using the number of components left.
Prove directly from the definition that deleting extra vertices from the sole remaining part cannot improve the minimum ratio for $K_{m,n}$.
For which positive integers $m,n$ with $m+n\geq3$ does $K_{m,n}$ fail the necessary toughness bound for Hamiltonicity?
If $t(K_{m,n})=1$, what does that imply about the Hamiltonicity test, and what does it not prove?