A Practical Method for Connectivity Problems
Connectivity questions often ask for three related but distinct quantities: how many vertices must be removed to disrupt a graph, how many edges must be removed, and how small a vertex degree is. These quantities can differ, so a numerical answer needs a certificate. An explicit separator or edge cut proves an upper bound; arguments that rule out smaller ones prove the matching lower bound. Menger’s theorem provides another kind of certificate by equating a minimum separator or cut with a maximum collection of disjoint paths between chosen terminals.
Throughout, graphs are finite and simple. A vertex separator for distinct nonadjacent vertices \(s,t\) is a set \(S\subseteq V(G)\setminus\{s,t\}\) such that deleting \(S\) leaves no \(s\)-\(t\) path. An edge cut separating \(s,t\) is a set of edges whose deletion leaves no \(s\)-\(t\) path. A global edge cut disconnects a connected graph.
For distinct nonadjacent terminals, Menger’s vertex theorem says that the maximum number of pairwise internally vertex-disjoint \(s\)-\(t\) paths equals the minimum size of an \(s\)-\(t\) vertex separator. “Internally vertex-disjoint” means the paths share no vertices other than \(s,t\). The edge version says that the maximum number of pairwise edge-disjoint \(s\)-\(t\) paths equals the minimum size of an \(s\)-\(t\) edge cut. These are the forms of Menger’s theorem used below; its proofs are part of the earlier material on vertex splitting and augmenting paths.
Proof. Each \(s\)-\(t\) path must meet any \(s\)-\(t\) vertex separator at an internal vertex. Since the \(k\) paths have disjoint internal vertices, a separator must contain at least \(k\) vertices. The exhibited separator has exactly \(k\), so it is minimum. The exhibited paths show that the maximum packing is at least \(k\); a separator of size \(k\), together with Menger’s theorem, shows it is at most \(k\). For edges, every path must use an edge of any separating edge set, and edge-disjoint paths use distinct such edges. The same lower-bound and equality argument applies. \(\square\)
Worked Certificates
Worked Example: A Cycle with a Chord
Let \(G\) have \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,45,51,13\}\). Find \(\delta(G)\), \(\kappa(G)\), and \(\lambda(G)\), then certify a path-packing value between \(2\) and \(5\).
The degrees, computed from the listed incident edges, are \(\deg(1)=3\) (edges \(12,51,13\)), \(\deg(2)=2\) (edges \(12,23\)), \(\deg(3)=3\) (edges \(23,34,13\)), \(\deg(4)=2\) (edges \(34,45\)), and \(\deg(5)=2\) (edges \(45,51\)). Thus \(\delta(G)=2\).
Deleting one vertex never disconnects the graph: the five cycle edges \(12,23,34,45,51\) form a cycle, and deleting any one of its vertices leaves a connected path on the other four. Hence \(\kappa(G)\ge2\). Deleting vertices \(1\) and \(3\) isolates vertex \(2\) from vertices \(4,5\), so \(\kappa(G)\le2\), and therefore \(\kappa(G)=2\).
Every edge lies on a cycle: the five cycle edges lie on the 5-cycle, while edge \(13\) lies on triangle \(1,2,3,1\). Thus no edge is a bridge. A one-edge cut in a connected graph would consist of a bridge, so \(\lambda(G)\ge2\). The two edges \(12,23\) are all the edges incident with vertex \(2\); deleting them isolates \(2\), giving \(\lambda(G)\le2\). Therefore \(\lambda(G)=2\).
For terminals \(s=2,t=5\), consider \(P_1=2,1,5\) and \(P_2=2,3,4,5\). They have no common internal vertex, and no common edge. The set \(\{1,4\}\) separates \(2\) from \(5\): after deleting it, the remaining edges are \(23\), and vertex \(5\) is isolated. The edge set \(\{12,23\}\) also separates the terminals, by isolating \(2\). Each separator or cut has size \(2\), matching the two paths.
Check: Menger’s theorem gives vertex and edge path-packing values of \(2\) for this terminal pair. Directly, the two paths have internal vertex sets \(\{1\}\) and \(\{3,4\}\), and their edge sets are disjoint. The displayed separators and cut rule out a third path of either kind.
Worked Example: Two Triangles Joined by a Bridge
Let \(G\) have \(V=\{a,b,c,d,e,f\}\) and \(E=\{ab,bc,ca,de,ef,fd,cd\}\). The first three edges form a triangle, the next three form another, and \(cd\) joins them. Compute the three parameters and use Menger’s theorem for \(a,e\).
The vertices \(a,b,e,f\) each have degree \(2\), while \(c,d\) each have degree \(3\). Hence \(\delta(G)=2\). Edge \(cd\) is the only edge joining the two triangles; deleting it disconnects the graph, so it is a bridge and \(\lambda(G)\le1\). Since \(G\) is connected, deleting zero edges does not disconnect it, and thus \(\lambda(G)=1\).
Deleting \(c\) separates \(a,b\) from \(d,e,f\), so \(\kappa(G)\le1\). The graph is connected, so deleting zero vertices does not disconnect it or leave at most one vertex. Thus \(\kappa(G)=1\).
The vertices \(a,e\) are nonadjacent. There is a path \(a,c,d,e\), and \(\{c\}\) separates \(a\) from \(e\). Menger’s vertex theorem therefore gives a maximum of exactly one internally vertex-disjoint \(a\)-\(e\) path. The edge cut \(\{cd\}\) separates them, and the displayed path gives one edge-disjoint path, so the edge-packing value is also exactly one.
Check: the parameter values are \((\kappa(G),\lambda(G),\delta(G))=(1,1,2)\). In particular, minimum degree \(2\) does not prevent a one-vertex separator or a one-edge cut.
Worked Example: Two Complete Graphs Sharing One Vertex
Let \(G\) consist of two copies of \(K_4\) sharing only vertex \(c\). Explicitly, let \(V=\{c,a,b,d,e,f,g\}\) and let \(E\) contain every pair among \(\{c,a,b,d\}\) and every pair among \(\{c,e,f,g\}\), with no other edges. Compute the parameters and find an edge-packing certificate between \(a\) and \(e\).
Each of \(a,b,d,e,f,g\) has degree \(3\), and \(c\) has degree \(6\), since it is joined to all six other vertices. Thus \(\delta(G)=3\). Deleting \(c\) separates \(\{a,b,d\}\) from \(\{e,f,g\}\), giving \(\kappa(G)\le1\); connectedness gives \(\kappa(G)\ge1\). Hence \(\kappa(G)=1\).
To prove \(\lambda(G)\ge3\), take any nontrivial partition of the vertices into \(S\) and \(V\setminus S\). Put \(c\) on the \(V\setminus S\) side, interchanging the names of the sides if needed. If \(S\) contains \(k\) of \(\{a,b,d\}\), the first \(K_4\) contributes \(k(4-k)\) crossing edges: each of those \(k\) vertices is adjacent to the other \(3-k\) vertices in that group and to \(c\). For \(k=1,2,3\), the contributions are respectively \(3,4,3\); for \(k=0\), it contributes \(0\). The same calculation applies to the group \(\{e,f,g\}\). Since \(S\) is nonempty, at least one group has \(k\ge1\), so at least \(3\) edges cross the partition. Therefore every edge cut has size at least \(3\). The three edges \(ac,ab,ad\) are all incident with \(a\); deleting them isolates \(a\), so \(\lambda(G)\le3\). Thus \(\lambda(G)=3\).
Between \(a\) and \(e\), the paths \(a,c,e\), \(a,b,c,f,e\), and \(a,d,c,g,e\) are edge-disjoint. Their edge sets are, respectively, \(\{ac,ce\}\), \(\{ab,bc,cf,fe\}\), and \(\{ad,dc,cg,ge\}\), with no edge repeated. The three edges \(\{ac,ab,ad\}\) separate \(a\) from \(e\), so the edge-packing value is exactly \(3\) by Menger’s theorem.
Check: the cut has size \(3\), and each of the three paths uses a different edge incident with \(a\). The calculation establishes \((\kappa(G),\lambda(G),\delta(G))=(1,3,3)\): the shared vertex makes vertex connectivity small even though every edge cut has size at least \(3\).
How to Build a Complete Solution
A useful order of work is to calculate degrees, search for small cuts, and then prove no smaller cut exists. The degree calculation gives the immediate upper bound \(\lambda(G)\le\delta(G)\) for a connected graph: isolating a minimum-degree vertex requires deleting its incident edges. To turn an apparent value into a proof, match each upper bound with a lower-bound argument. For vertex connectivity, check that every deletion of fewer vertices leaves the graph connected. For edge connectivity, show every nontrivial partition has enough crossing edges, or rule out cuts of each smaller size.
List incident edges and identify \(\delta(G)\). This immediately supplies an edge-cut candidate at a minimum-degree vertex.
Delete it and state which terminals or vertex groups are disconnected. This proves an upper bound, not yet equality.
Check smaller vertex deletions or edge partitions using the structure of the graph. State why the argument covers every possibility.
Exhibit paths with the required disjointness, then exhibit a separator or cut of the same size. Menger’s theorem certifies optimality.
Common Pitfall: Confusing Degree with Connectivity
A common incorrect calculation is to observe that the two-\(K_4\) graph in the last example has minimum degree \(3\), then conclude \(\kappa(G)=3\). That substitutes a degree for a vertex-deletion calculation. In fact, deleting the single vertex \(c\) disconnects the two groups, so \(\kappa(G)=1\), while \(\delta(G)=3\) and \(\lambda(G)=3\). Degree is useful for bounding edge connectivity, but it does not by itself determine vertex connectivity.
Likewise, listing several paths does not establish that the packing is maximum. The paths give a lower bound. A matching separator or cut supplies the upper bound, and Menger’s theorem turns the two matching bounds into an exact value. Always name the terminals and check that the paths have the required disjointness: internally vertex-disjoint paths may share edges only if those edges are incident to a shared endpoint, whereas edge-disjoint paths may share vertices.
Check Your Understanding
For each question, give the supporting path, separator, cut, or lower-bound argument as appropriate.
- In the first worked example, why does the pair \(\{1,4\}\) separate \(2\) from \(5\), and why does that not alone prove the global value of \(\kappa(G)\)?
- For two triangles joined by a single edge, identify a vertex separator and an edge cut witnessing the values of \(\kappa\) and \(\lambda\).
- In the shared-\(K_4\) example, compute the number of crossing edges contributed by a group when \(k=2\) of its three nonshared vertices lie on one side of a cut.
- Explain why three edge-disjoint paths give a lower bound of three on every edge cut separating their terminals.
- Give a graph in which \(\delta(G)\) and \(\kappa(G)\) differ, and identify a set of vertices whose deletion certifies the smaller value.