Connectivity as a Failure Threshold
Connectivity gives a worst-case measure of how many network elements must fail before the network loses connected operation. Vertex connectivity counts failed vertices, together with all their incident edges; edge connectivity counts failed edges while retaining every vertex. These are different failure models, so their values need not agree.
All graphs in this tutorial are finite and simple. For a graph \(G=(V,E)\), deleting a set \(S\subseteq V\) means removing the vertices in \(S\) and every edge incident to them; the remaining graph is denoted \(G-S\). For \(F\subseteq E\), \(G-F\) retains all vertices and deletes just the edges in \(F\). A graph is connected if every two distinct vertices can be joined by a path. A graph with at least two vertices that is not connected is disconnected.
The convention for vertex connectivity treats a network reduced to one active vertex as no longer operating as a connected network between distinct terminals. It is also what gives \(\kappa(K_n)=n-1\) for complete graphs with \(n\ge 2\). For a one-vertex graph, the stated convention applies. In a disconnected graph the network has already lost connected operation, so no failures are needed.
These numbers concern the smallest destructive failure set. They do not say that every set of that size is destructive. They do say that every smaller failure set is harmless with respect to disconnection, under the specified failure model.
What the Threshold Guarantees
Proof. The graph is finite, so there are finitely many vertex sets and edge sets to consider. Deleting all but one vertex is an allowed vertex failure set, so at least one qualifying set exists in the definition of \(\kappa(G)\). Deleting all edges is a qualifying edge failure set when \(|V|\ge2\), so one exists for \(\lambda(G)\). Each minimum is therefore attained. If a vertex set of size less than \(\kappa(G)\) caused disconnection or left at most one vertex, it would be a qualifying set smaller than the minimum, a contradiction. A set attaining the minimum has the stated effect by definition. The same minimum argument for edge sets proves both edge claims. \(\square\)
“Always leaves connected” is a worst-case guarantee over all failure patterns of the specified size. The theorem does not predict which individual component, route, or service will be lost, and it says nothing about simultaneous vertex and edge failures. Those are different questions from either connectivity parameter alone.
Edge Failures and Cuts
For a nonempty proper subset \(X\subset V\), write \(E(X,V\setminus X)\) for the edges with one endpoint in \(X\) and the other in \(V\setminus X\). Such edges cross the partition of the vertices into \(X\) and its complement. A cut separating a partition consists of those crossing edges.
Proof. Fix a nonempty proper set \(X\). If every edge in \(E(X,V\setminus X)\) is deleted, no remaining edge joins a vertex of \(X\) to a vertex outside \(X\). A path from \(X\) to \(V\setminus X\) would have to use such an edge, so the resulting graph is disconnected. Thus \(\lambda(G)\le |E(X,V\setminus X)|\) for every such \(X\).
Conversely, take an edge set \(F\) whose deletion disconnects \(G\). Choose the vertex set \(X\) of one connected component of \(G-F\). This set is nonempty and proper. Every original edge crossing from \(X\) to \(V\setminus X\) must belong to \(F\); otherwise that edge would still join the component to a vertex outside it in \(G-F\). Hence \(|E(X,V\setminus X)|\le |F|\). Apply this to a minimum disconnecting set \(F\): the minimum partition cut is no larger than \(\lambda(G)\). Combined with the first inequality, this proves the equality. \(\square\)
This characterization makes edge resilience a partition question: find the least number of links crossing any nontrivial division of the vertices. Vertex resilience instead asks how many vertices must be removed. A set of failed vertices also removes their incident edges, but that does not make the two failure models interchangeable.
Worked Example: Resilience of a Six-Cycle
Let \(G\) have vertex set \(V=\{1,2,3,4,5,6\}\) and edge set \(E=\{12,23,34,45,56,61\}\). Each vertex has degree \(2\), so \(\delta(G)=2\).
Deleting vertex \(1\) leaves the path with vertices \(2,3,4,5,6\) and edges \(23,34,45,56\), which is connected. By the symmetry of the cycle, deleting any one vertex leaves a connected path. Deleting vertices \(1\) and \(4\), however, leaves edges \(23\) and \(56\), with no edge between the two remaining components. Thus one vertex failure never suffices, but two can, so \(\kappa(G)=2\).
Deleting edge \(12\) alone leaves the path with edges \(23,34,45,56,61\), which is connected. Deleting \(12\) and \(45\) leaves two components: vertices \(2,3,4\) joined by \(23,34\), and vertices \(5,6,1\) joined by \(56,61\). Thus \(\lambda(G)=2\).
Check: The edge-cut characterization agrees. For any nonempty proper vertex subset of a cycle, at least two cycle edges cross between it and its complement: moving around the cycle must enter the subset and later leave it. The partition \(X=\{1,2,3\}\), \(V\setminus X=\{4,5,6\}\) has exactly the two crossing edges \(34\) and \(61\). Hence the minimum cut has size \(2\), as calculated directly.
Vertex and Edge Resilience Can Differ
Worked Example: Two Complete Graphs Sharing One Vertex
Let \(G\) have vertex set \(V=\{a,b,c,d,e,f,g\}\) and edge set \(E=\{ab,ac,ad,bc,bd,cd,ae,af,ag,ef,eg,fg\}\). The vertices \(a,b,c,d\) form one \(K_4\), and \(a,e,f,g\) form another; the two copies share only \(a\).
Deleting \(a\) leaves one triangle on \(\{b,c,d\}\) and another on \(\{e,f,g\}\), with no edge between them. The original graph is connected, so zero vertex failures do not disconnect it and one does. Therefore \(\kappa(G)=1\). Notice that deleting \(b\) instead leaves a connected graph: the shared vertex \(a\) still joins the two sides. Thus not every single vertex failure is destructive.
To compute \(\lambda(G)\), consider any partition of the vertices into two nonempty parts. At least one of the two \(K_4\) subgraphs must be split by the partition: if neither were split, both would lie wholly in the same part because they share \(a\), leaving the other part empty. If a \(K_4\) is split into groups of sizes \(x\) and \(4-x\), where \(x\in\{1,2,3\}\), the number of crossing edges inside it is \(x(4-x)\). The three possible values are \(1\cdot3=3\), \(2\cdot2=4\), and \(3\cdot1=3\). Consequently every partition cut has at least three edges. Isolating \(b\) gives a cut consisting of \(ab,bc,bd\), exactly three edges, so \(\lambda(G)=3\).
Check: The degree of each of \(b,c,d,e,f,g\) is \(3\), while \(a\) is adjacent to all six other vertices and has degree \(6\). Hence \(\delta(G)=3\), consistent with the edge-cut calculation. The vertex and edge failure thresholds differ: one failed vertex, \(a\), disconnects the graph, whereas at least three failed edges are needed.
Complete Graphs and the Boundary Convention
Worked Example: Resilience of \(K_5\)
Let \(G=K_5\), with \(V=\{1,2,3,4,5\}\) and \(E=\{ij:1\le i<j\le5\}\). There are \(5\cdot4/2=10\) edges, and each vertex has degree \(4\).
Deleting three vertices leaves two vertices joined by their edge, so the remaining graph is connected. Deleting four vertices leaves one vertex, which meets the stated failure convention. Therefore \(\kappa(K_5)=4\).
For edge failures, partition the vertices into parts of sizes \(s\) and \(5-s\), with \(s\in\{1,2,3,4\}\). Since every pair in opposite parts is adjacent, the cut has \(s(5-s)\) edges. The values are \(1\cdot4=4\), \(2\cdot3=6\), \(3\cdot2=6\), and \(4\cdot1=4\). Thus the smallest cut has size \(4\), and \(\lambda(K_5)=4\). For instance, deleting the four edges incident to vertex \(1\) isolates it.
Check: The cut separating vertex \(1\) has four crossing edges, while the other four vertices retain their \(\binom{4}{2}=4\cdot3/2=6\) edges. The count \(4+6=10\) agrees with the total edge count, and the calculated edge-failure threshold is \(4\).
Common Pitfall: Minimum Degree Is Not Vertex Connectivity
A tempting but incorrect calculation is to infer \(\kappa(G)=\delta(G)\) from the fact that every vertex has many neighbors. The shared-\(K_4\) example shows why this fails. Every vertex other than \(a\) has degree \(3\), and \(a\) has degree \(6\), so the minimum degree is \(3\). Nevertheless, deleting the single shared vertex \(a\) disconnects the graph, giving \(\kappa(G)=1\), not \(3\).
The distinction is structural. A vertex can be a bottleneck connecting large groups even when every other vertex has several neighbors. Similarly, \(\lambda(G)\) is a minimum over edge cuts, not a statement that every set of \(\lambda(G)\) failed edges disconnects the graph. Connectivity values describe worst-case thresholds: they guarantee survival below the threshold and certify the existence of a destructive pattern at the threshold.
Check Your Understanding
Use the definitions and the cut characterization to justify each answer.
- In a connected graph with \(\kappa(G)=3\), what does the value guarantee after two vertex failures, and what does it say about some set of three failures?
- For the cycle \(C_6\) in the worked example, give a different pair of edges whose deletion disconnects the graph.
- Explain why \(\lambda(G)\) is the minimum size of a partition cut, rather than the number of edges incident to a minimum-degree vertex in every graph.
- For \(K_5\), how many vertex failures leave exactly two vertices, and are those two vertices connected?
- In the shared-\(K_4\) graph, why does deleting a non-shared vertex not disconnect the two triangles’ sides from one another?