Three Parameters for Complete Graphs
Complete graphs and complete bipartite graphs have enough symmetry that their connectivity parameters can be calculated exactly. The answers are closely related: in each family, the vertex connectivity \(\kappa\), edge connectivity \(\lambda\), and minimum degree \(\delta\) are equal. To use that fact correctly, however, we must distinguish deleting vertices from deleting edges and handle graphs with very few vertices explicitly.
All graphs in this tutorial are finite and simple. A graph is connected if every pair of its vertices can be joined by a path. For a connected graph, a vertex cut is a set of vertices whose deletion leaves a disconnected graph or a graph with at most one vertex. The vertex connectivity \(\kappa(G)\) is the minimum size of such a set. For a graph already disconnected, set \(\kappa(G)=0\). An edge cut is a set of edges whose deletion disconnects the graph. For a connected graph with at least two vertices, \(\lambda(G)\) is the minimum size of an edge cut. Set \(\lambda(G)=0\) for a disconnected graph or a graph with fewer than two vertices. These conventions make \(\kappa(K_1)=\lambda(K_1)=0\). The minimum degree is \(\delta(G)=\min_{v\in V(G)}\deg(v)\) for a graph with at least one vertex.
Proof. If \(n=1\), the graph has one vertex and no edges. By the conventions above, \(\kappa(K_1)=\lambda(K_1)=0\), and its only vertex has degree \(0\). Now suppose \(n\ge2\). Every vertex of \(K_n\) is adjacent to all other \(n-1\) vertices, so \(\delta(K_n)=n-1\). Deleting fewer than \(n-1\) vertices leaves at least two vertices, and the remaining graph is complete and connected. Deleting \(n-1\) vertices leaves a single vertex, so \(\kappa(K_n)=n-1\).
For the edge parameter, consider any partition of the vertices into two nonempty sets of sizes \(s\) and \(n-s\). Exactly \(s(n-s)\) edges have one endpoint in each set. If deleting edges disconnects \(K_n\), the vertices in some component and the vertices outside it give such a partition, and every edge crossing that partition must have been deleted. Thus at least \(s(n-s)\) edges were deleted. Since $$ s(n-s)-(n-1)=(s-1)(n-s-1)\ge0, $$ every edge cut has at least \(n-1\) edges. Deleting the \(n-1\) edges incident with one chosen vertex isolates it, so \(\lambda(K_n)=n-1\). \(\square\)
Worked Example: The Complete Graph \(K_5\)
Let \(G=K_5\), with \(V(G)=\{1,2,3,4,5\}\) and \(E(G)=\{ij:1\le i<j\le5\}\). Each vertex is adjacent to the other four, so \(\delta(G)=4\). Removing fewer than four vertices leaves at least two vertices, and those remaining vertices still form a complete graph. Removing vertices \(2,3,4,5\) leaves just vertex \(1\). Therefore \(\kappa(G)=4\).
To disconnect the graph by edge deletion, isolate vertex \(1\) by deleting \(12,13,14,15\), giving an edge cut of size \(4\). Conversely, every nontrivial partition has \(s\) vertices on one side and \(5-s\) on the other, where \(s\in\{1,2,3,4\}\). The crossing-edge counts are \(1\cdot4=4\), \(2\cdot3=6\), \(3\cdot2=6\), and \(4\cdot1=4\). No partition has fewer than four crossing edges, so \(\lambda(G)=4\).
Check: the formula gives \(n-1=5-1=4\) for all three parameters, matching the direct vertex and edge cut calculations.
Complete Bipartite Graphs
For positive integers \(m,n\), the complete bipartite graph \(K_{m,n}\) has two disjoint vertex parts \(A\) and \(B\), with \(|A|=m\) and \(|B|=n\). Its edge set consists of every pair with one endpoint in \(A\) and one in \(B\), and no pairs within either part. If a vertex lies in \(A\), its degree is \(n\); if it lies in \(B\), its degree is \(m\). Consequently, \(\delta(K_{m,n})=\min(m,n)\).
Proof. Interchanging the names of the parts if necessary, assume \(m\le n\). The degree calculation gives \(\delta(K_{m,n})=m\). If fewer than \(m\) vertices are deleted, at least one vertex remains in each part: fewer than \(m\) deletions cannot remove all \(m\) vertices of \(A\), or all \(n\) vertices of \(B\). The remaining graph is connected. Indeed, vertices in opposite parts are adjacent, and any two vertices in the same part have a path of length two through a remaining vertex in the other part. Thus fewer than \(m\) deletions cannot disconnect the graph or leave at most one vertex. Deleting all \(m\) vertices of \(A\) leaves \(n\) vertices and no edges. If \(n>1\), the remaining graph is disconnected; if \(n=1\), it is a single vertex. In either case this deletion qualifies as a vertex cut, so \(\kappa(K_{m,n})=m\).
For the edge parameter, take any nontrivial partition of the vertices into sets \(S\) and \(V(G)\setminus S\). Write \(a=|S\cap A|\) and \(b=|S\cap B|\). The number of crossing edges is $$ f(a,b)=a(n-b)+(m-a)b. $$ The first term counts edges from \(S\cap A\) to \(B\setminus S\), and the second counts edges from \(A\setminus S\) to \(S\cap B\). We show this count is at least \(m\). If \(a=0\), then \(S\) is nonempty, so \(b\ge1\), and \(f(0,b)=mb\ge m\). If \(a=m\), then the partition is nontrivial only if \(b<n\), and \(f(m,b)=m(n-b)\ge m\). If \(0<a<m\), regard the expression as a function of \(b\). It is linear in \(b\), with endpoint values \(f(a,0)=an\ge m\) and \(f(a,n)=(m-a)n\ge n\ge m\). Every value for \(0\le b\le n\) lies between these endpoint values, so \(f(a,b)\ge m\).
Whenever deleting edges disconnects a connected graph, the vertices of a resulting component and the vertices outside it form a nontrivial partition; all edges crossing that partition must have been deleted. The calculation therefore proves that at least \(m\) edges must be deleted. On the other hand, any vertex in \(B\) has degree \(m\); deleting its \(m\) incident edges isolates it. Hence \(\lambda(K_{m,n})=m\), completing the proof. \(\square\)
Worked Example: The Complete Bipartite Graph \(K_{2,4}\)
Let \(A=\{a_1,a_2\}\), \(B=\{b_1,b_2,b_3,b_4\}\), and let \(G=K_{2,4}\), with \(V(G)=A\cup B\) and \(E(G)=\{a_i b_j:1\le i\le2,\ 1\le j\le4\}\). Each vertex in \(A\) has degree \(4\), and each vertex in \(B\) has degree \(2\). Thus \(\delta(G)=2\).
Removing \(a_1\) alone leaves \(K_{1,4}\), which is connected, and removing no vertices also leaves a connected graph. Removing both vertices of \(A\) leaves the four vertices of \(B\) with no edges, a disconnected graph. Hence \(\kappa(G)=2\). For an edge cut of size \(2\), delete the two edges \(a_1b_1\) and \(a_2b_1\), isolating \(b_1\). The theorem's partition calculation shows no edge cut has fewer than \(\min(2,4)=2\) edges, so \(\lambda(G)=2\).
Check: \(\min(2,4)=2\), which agrees with the degree calculation, the two-vertex cut, and the two-edge cut.
Worked Example: The Star \(K_{1,3}\)
Let \(A=\{c\}\), \(B=\{x,y,z\}\), and \(G=K_{1,3}\), with \(E(G)=\{cx,cy,cz\}\). The center \(c\) has degree \(3\), and each of \(x,y,z\) has degree \(1\), so \(\delta(G)=1\). Deleting \(c\) leaves three isolated vertices, so \(\kappa(G)\le1\); since the graph is connected before any deletion, \(\kappa(G)=1\). Deleting the single edge \(cx\) isolates \(x\), while zero edge deletions leave the graph connected. Thus \(\lambda(G)=1\).
Check: the formula gives \(\min(1,3)=1\) for \(\kappa\), \(\lambda\), and \(\delta\). This example also shows that a vertex cut and an edge cut need not have the same elements, even when their sizes agree.
Smallest Cases and a Common Mistake
Worked Example: \(K_1\) and \(K_{1,1}\)
The graph \(K_1\) has \(V=\{v\}\) and \(E=\varnothing\). Its only degree is \(0\), so \(\delta(K_1)=0\). It is not disconnected, but its order is already at most one; deleting zero vertices meets the stated vertex-cut condition, so \(\kappa(K_1)=0\). There is no edge to delete, and our convention gives \(\lambda(K_1)=0\). The complete-graph formula also gives \(1-1=0\).
Now let \(G=K_{1,1}\), with \(A=\{u\}\), \(B=\{v\}\), and \(E(G)=\{uv\}\). Both degrees are \(1\), so \(\delta(G)=1\). Deleting \(u\) leaves one vertex, while deleting no vertices leaves a connected graph; hence \(\kappa(G)=1\). Deleting the only edge disconnects the two vertices, so \(\lambda(G)=1\). Here \(K_{1,1}=K_2\), and both formulas give \(1\).
Check: the one-vertex graph and the one-edge graph have different parameter values: \(0,0,0\) for \(K_1\), and \(1,1,1\) for \(K_{1,1}\). The distinction follows from their orders and edge sets, not from an exception to the formulas.
Common mistake: choosing the wrong part to isolate. In \(K_{2,4}\), isolating a vertex from the smaller part \(A\) takes \(4\) edge deletions, because that vertex has degree \(4\). Concluding from this that \(\lambda(K_{2,4})=4\) is wrong: a vertex in the larger part \(B\) has degree \(2\), and deleting its two incident edges already disconnects the graph. The correction is to compare both part sizes: the minimum degree is \(\min(2,4)=2\), and the theorem proves that no smaller edge cut is possible.
If a convention permits an empty part in the notation \(K_{m,n}\), handle it separately rather than applying the theorem, which assumes \(m,n\ge1\). For example, \(K_{0,n}\) has no edges: if \(n>1\), it is disconnected and has \(\kappa=\lambda=\delta=0\); if \(n=1\), it is \(K_1\). The empty graph has no minimum degree under the definition used here, since it has no vertices over which to take a minimum.
The formulas are useful because they give immediate exact values without enumerating all possible separators. Their proofs also clarify what certifies each value: for vertex connectivity, a smallest part can be removed; for edge connectivity, a minimum-degree vertex can be isolated. Matching these upper bounds requires the lower-bound arguments: the remaining complete or complete bipartite graph stays connected after too few vertex deletions, and every nontrivial partition has enough crossing edges to require at least the claimed number of edge deletions.
Check Your Understanding
For each question, distinguish vertex deletion from edge deletion and state any boundary convention you use.
- Calculate \(\delta(K_7)\), \(\kappa(K_7)\), and \(\lambda(K_7)\). Give a vertex cut and an edge cut attaining the two connectivity values.
- For \(K_{3,5}\), how many vertices must be deleted to leave a disconnected graph, and how many edges suffice to disconnect it?
- In \(K_{1,6}\), which vertex has minimum degree? Give a one-edge cut and a one-vertex cut.
- Why does deleting fewer than \(\min(m,n)\) vertices from \(K_{m,n}\), for positive \(m,n\), leave at least one vertex in each part?
- Explain why \(\lambda(K_{1,1})=1\) but \(\lambda(K_1)=0\) under the conventions in this tutorial.