Why Sharpness Examples Matter
The bounds \(\kappa(G)\le\lambda(G)\le\delta(G)\) compare three different ways a graph can fail under deletion. They need not have the same value: a graph may lose connectivity after removing one vertex even though several edges must be removed, or it may have vertices of relatively high degree while only a few edges link two large regions. To understand what the inequalities do and do not say, it helps to verify graphs where one inequality is strict and graphs where both are equalities.
All graphs in this tutorial are finite, simple, undirected, and connected. For the graphs considered here, a vertex cut is a set \(S\subseteq V(G)\) such that deleting \(S\) leaves a disconnected graph; \(\kappa(G)\) is the minimum size of such a set. An edge cut is a set of edges whose deletion disconnects the graph; \(\lambda(G)\) is the minimum size of such a set. The minimum degree is \(\delta(G)=\min_{v\in V(G)}\deg(v)\). We will verify each parameter directly rather than infer it from the inequality.
The earlier result \(\kappa(G)\le\lambda(G)\le\delta(G)\), derived from Menger’s theorem, guarantees that the examples below fit the general bounds. The point here is to see exactly how strictness and equality arise in explicit graphs.
Vertex Connectivity Can Be Strictly Smaller
Worked Example: Two Complete Graphs Sharing One Vertex
Let \(G\) have vertex set \(V=\{h,a,b,c,d,e,f\}\) and edge set \(E=\{ha,hb,hc,ab,ac,bc,hd,he,hf,de,df,ef\}\). Thus the vertices \(\{h,a,b,c\}\) induce a \(K_4\), and \(\{h,d,e,f\}\) induce another \(K_4\); the two share only \(h\).
The degree of \(h\) is \(6\), since it is adjacent to \(a,b,c,d,e,f\). Each of the other six vertices has degree \(3\): for example, \(a\) is adjacent to \(h,b,c\), and \(d\) is adjacent to \(h,e,f\). Therefore \(\delta(G)=3\). As a count check, the edge list has \(6+6=12\) edges, and the degree sum is \(6+6\cdot3=24=2|E|\).
Deleting \(h\) separates \(\{a,b,c\}\) from \(\{d,e,f\}\), so \(\kappa(G)\le1\). The graph is connected, so deleting no vertices does not disconnect it. Hence \(\kappa(G)=1\).
For the edge connectivity, deleting the three edges \(ha,hb,hc\) separates \(\{a,b,c\}\) from \(\{h,d,e,f\}\), so \(\lambda(G)\le3\). To prove the matching lower bound, consider any edge cut, and place the vertices on the two sides of the resulting partition. If a \(K_4\) is split between the sides, at least three of its edges cross: a split with \(r\) vertices on one side has \(r(4-r)\) crossing edges, which is \(3\) when \(r=1\) or \(3\), and \(4\) when \(r=2\). Every nontrivial partition must split at least one of the two \(K_4\) subgraphs. Otherwise each \(K_4\) would lie wholly on one side, and because both contain \(h\), they would lie on the same side, leaving the other side empty. Thus every edge cut has size at least \(3\), and \(\lambda(G)=3\).
Check: the verified values are \(\kappa(G)=1\), \(\lambda(G)=3\), and \(\delta(G)=3\). Consequently, \(\kappa(G)<\lambda(G)=\delta(G)\).
This graph illustrates how a single shared vertex can be a bottleneck even when each of the two dense pieces requires at least three edge deletions to separate internally. Vertex and edge cuts measure different kinds of vulnerability, so their minima need not agree.
Edge Connectivity Can Be Strictly Smaller
Worked Example: Two Dense Pieces Joined by Two Edges
Let \(G\) have vertex set \(V=L\cup R\), where \(L=\{a_1,a_2,a_3,a_4\}\) and \(R=\{b_1,b_2,b_3,b_4\}\). Its edges are all pairs of distinct vertices within \(L\), all pairs of distinct vertices within \(R\), and the two additional edges \(a_1b_1\) and \(a_2b_2\). In other words, each side induces a \(K_4\), and the only edges between the sides are \(a_1b_1\) and \(a_2b_2\).
Each \(K_4\) contributes \(6\) edges, so \(|E(G)|=6+6+2=14\). The four vertices \(a_1,a_2,b_1,b_2\) have degree \(4\), while \(a_3,a_4,b_3,b_4\) have degree \(3\). Thus \(\delta(G)=3\), and the degree sum is \(4\cdot4+4\cdot3=28=2|E(G)|\).
Deleting the two edges between \(L\) and \(R\) disconnects the graph, so \(\lambda(G)\le2\). To show that no single edge disconnects it, consider any partition of the vertices into two nonempty sides. If either \(K_4\) is split, at least three edges of that \(K_4\) cross the partition, by the count \(r(4-r)\ge3\) for \(1\le r\le3\). If neither \(K_4\) is split, each lies wholly on one side. Since the partition is nontrivial, \(L\) and \(R\) must be on opposite sides, and both joining edges cross. Every edge cut therefore has size at least \(2\), proving \(\lambda(G)=2\).
For vertex connectivity, deleting \(a_1\) and \(a_2\) removes both joining edges. The remaining vertices in \(L\) and \(R\) are nonempty, and there is no edge between them, so \(\kappa(G)\le2\). On the other hand, deleting any single vertex leaves each \(K_4\) with at least three vertices, which form a connected subgraph. At most one of the two joining edges is lost when one vertex is deleted, because their endpoints are distinct. The other joining edge remains, connecting the surviving portions of \(L\) and \(R\). Thus no single vertex disconnects \(G\), and \(\kappa(G)=2\).
Check: \(\kappa(G)=2\), \(\lambda(G)=2\), and \(\delta(G)=3\), so \(\kappa(G)=\lambda(G)<\delta(G)\). The two joining edges are an edge cut even though every vertex has degree at least \(3\).
The lower-bound arguments in these examples use the same useful pattern: take an arbitrary partition created by a proposed cut and count how many edges must cross it. A small cut can be identified by inspection, but proving that it is minimum requires excluding all smaller possibilities.
Both Inequalities Can Be Equalities
Worked Example: The House Graph
Let \(H\) have vertex set \(V=\{1,2,3,4,5\}\) and edge set \(E=\{12,23,34,41,25,53\}\). The first four edges form the cycle \(1,2,3,4,1\), and vertex \(5\) is adjacent to \(2\) and \(3\).
The degrees are \(\deg(1)=2\), \(\deg(2)=3\), \(\deg(3)=3\), \(\deg(4)=2\), and \(\deg(5)=2\); hence \(\delta(H)=2\). There are six listed edges, and the degree sum is \(2+3+3+2+2=12=2\cdot6\).
Removing vertices \(2\) and \(4\) leaves vertices \(1,3,5\). Vertex \(1\) is isolated, while \(3\) and \(5\) are adjacent, so this is a vertex cut and \(\kappa(H)\le2\). We now check that no single vertex is a cut. Removing \(1\) leaves the connected edges \(2\!-\!3\), \(3\!-\!4\), and \(2\!-\!5\) (among others). Removing \(2\) leaves the connected path \(1\!-\!4\!-\!3\!-\!5\). Removing \(3\) leaves the connected path \(4\!-\!1\!-\!2\!-\!5\). Removing \(4\) leaves the connected edges \(1\!-\!2\), \(2\!-\!3\), and \(2\!-\!5\). Removing \(5\) leaves the original 4-cycle. Thus no one-vertex deletion disconnects \(H\), and \(\kappa(H)=2\).
The two edges \(12\) and \(14\) isolate vertex \(1\) when deleted, so \(\lambda(H)\le2\). To show that no one edge is enough, observe that each cycle edge \(12,23,34,41\) lies on the 4-cycle, and each edge \(25,53\) lies on the triangle \(2,3,5,2\). An edge lying on a cycle cannot be a one-edge cut: after it is deleted, the rest of that cycle still provides a path between its endpoints. Since every edge of \(H\) lies on one of these cycles, deleting any single edge leaves the graph connected. Therefore \(\lambda(H)=2\).
Check: \(\kappa(H)=2\), \(\lambda(H)=2\), and \(\delta(H)=2\). Thus both inequalities are equalities. The upper bounds come from explicit cuts, and the lower bounds come from checking all single-vertex deletions and ruling out every one-edge cut.
How to Read the Examples
The three constructions separate the roles of the parameters:
| Graph | \(\kappa(G)\) | \(\lambda(G)\) | \(\delta(G)\) | Relation |
|---|---|---|---|---|
| Two \(K_4\) subgraphs sharing one vertex | 1 | 3 | 3 | \(\kappa<\lambda=\delta\) |
| Two \(K_4\) subgraphs joined by two edges | 2 | 2 | 3 | \(\kappa=\lambda<\delta\) |
| House graph | 2 | 2 | 2 | \(\kappa=\lambda=\delta\) |
These examples demonstrate that neither inequality must be strict, and that either one can be strict while the other is an equality. They do not assert that every possible combination of values occurs for every graph class; each conclusion is supported by the specific cut and lower-bound checks above.
Common Pitfall: Minimum Degree Is Not an Edge-Cut Calculation
In the two-\(K_4\) example joined by two edges, a tempting but incorrect calculation is: “Every vertex has degree at least \(3\), so \(\lambda(G)=3\).” The degree calculation establishes only \(\delta(G)=3\), and the general inequality gives \(\lambda(G)\le\delta(G)\), not \(\lambda(G)=\delta(G)\). In fact, deleting the two joining edges disconnects the graph, so \(\lambda(G)\le2\); the partition argument proves \(\lambda(G)\ge2\), giving \(\lambda(G)=2\). Always distinguish the degree of an individual vertex from the number of edges crossing a cut between two larger groups.
A second useful check concerns vertex cuts: after deleting a proposed set, verify the remaining graph itself. A set is a cut only if the remaining vertices are disconnected; merely seeing that some edges have disappeared is not enough. In the examples above, each proposed cut was checked by identifying nonempty remaining pieces with no connection between them.
Check Your Understanding
For each question, justify your answer with either a cut or a lower-bound argument.
- In the two-\(K_4\)-sharing-a-vertex graph, why does deleting the shared vertex prove \(\kappa(G)\le1\), but not by itself prove \(\kappa(G)=1\)?
- In the graph formed from two \(K_4\) subgraphs joined by two edges, identify the edge cut that proves \(\lambda(G)\le2\).
- For that same graph, explain why deleting any one vertex leaves at least one joining edge.
- In the house graph, give a vertex cut of size \(2\) and list the remaining connected components.
- Why does knowing \(\delta(G)=3\) not establish \(\lambda(G)=3\)? Give the relevant cut in the second worked example.