Local Values and Global Minima
A graph’s global connectivity records how cheaply the graph can be separated, but it does not by itself say which vertices are most vulnerable. Pairwise connectivity makes that information explicit: it measures how many independent routes join a selected pair. Comparing the two viewpoints helps locate bottlenecks and distinguish a weak vertex separator from a weak edge cut.
All graphs in this tutorial are finite and simple. For distinct vertices \(u,v\), a \(u\)-\(v\) path has endpoints \(u\) and \(v\). A collection of paths is internally vertex-disjoint if no two paths share an internal vertex; the endpoints may be shared. It is edge-disjoint if no edge belongs to more than one path. A vertex set \(S\), with \(u,v\notin S\), separates \(u\) from \(v\) if \(u\) and \(v\) lie in different components of \(G-S\). An edge set \(F\) separates them if they lie in different components of \(G-F\).
The pairwise definitions count paths, while the global definitions count deletions. Menger’s theorem gives the precise bridge between them: in a connected noncomplete graph, \(\kappa(G)=\min_{u\ne v}\kappa_G(u,v)\), and in a connected graph with at least two vertices, \(\lambda(G)=\min_{u\ne v}\lambda_G(u,v)\). The vertex statement uses the standard endpoint convention for adjacent pairs. These are standard consequences of Menger’s theorem; its proofs come later in the course. Here we use the statements to organize examples, and verify the small-graph calculations directly where possible.
What a Cut Can Tell Us About a Pair
Even before using Menger’s theorem, a cut gives a useful upper bound. If a vertex set \(S\) separates nonadjacent vertices \(u,v\), every \(u\)-\(v\) path must contain a vertex of \(S\). In an internally vertex-disjoint collection, different paths must use different vertices of \(S\). Similarly, if an edge set \(F\) separates \(u,v\), every path uses an edge of \(F\), and edge-disjoint paths must use different such edges.
Proof. Consider first a collection of internally vertex-disjoint \(u\)-\(v\) paths. Since \(S\) separates the endpoints, each path contains at least one vertex of \(S\). None of these vertices is an endpoint, and two different paths cannot use the same internal vertex. Thus a collection of \(r\) such paths requires at least \(r\) distinct vertices of \(S\), so \(r\le |S|\). Taking the maximum over collections gives \(\kappa_G(u,v)\le |S|\). For the edge statement, every \(u\)-\(v\) path contains at least one edge of \(F\). Edge-disjoint paths use distinct edges of \(F\), so a collection of \(r\) paths has \(r\le |F|\), and maximizing gives \(\lambda_G(u,v)\le |F|\). \(\square\)
The nonadjacency condition in the vertex assertion matters: if \(u\) and \(v\) are adjacent, their edge \(uv\) remains a path after deleting any set of other vertices. The path-based definition of \(\kappa_G(u,v)\) still applies to adjacent pairs, but the separator bound above is stated only where a vertex separator can separate the pair.
Worked Examples
Worked Example: Two Triangles Sharing a Vertex
Let \(G\) have \(V=\{a,b,c,d,e\}\) and \(E=\{ab,bc,ca,cd,de,ec\}\). The triangles \(abc\) and \(cde\) share only \(c\). Determine the global parameters and some pairwise values.
Deleting \(c\) leaves the two components on \(\{a,b\}\) and \(\{d,e\}\), so \(\kappa(G)\le1\). The graph is connected, so deleting no vertices cannot disconnect it; hence \(\kappa(G)=1\). The pair \(a,d\) has only routes through \(c\). For example, \(a,c,d\) and \(a,b,c,e,d\) both use \(c\) internally, so they cannot be members of the same internally vertex-disjoint family. The paths \(a,c,d\) provide one route, and the separator \(\{c\}\) bounds the number by one. Thus \(\kappa_G(a,d)=1\).
Every edge belongs to one of the two triangles, so deleting any single edge leaves an alternate route between its endpoints and the whole graph remains connected. Therefore \(\lambda(G)\ge2\). The two edges incident with \(a\) form an edge cut separating \(a\) from the other vertices, so \(\lambda(G)\le2\), and \(\lambda(G)=2\). For the cross-pair \(a,d\), the paths \(a,c,d\) and \(a,b,c,e,d\) are edge-disjoint; the edge cut \(\{ab,ac\}\) separates \(a\) from \(d\). Consequently \(\lambda_G(a,d)=2\).
Check: The degrees are \(\deg(c)=4\) and \(\deg(a)=\deg(b)=\deg(d)=\deg(e)=2\). For any pair of distinct vertices, at least one endpoint is not \(c\), and that endpoint has degree \(2\). Its two incident edges separate it from the other endpoint, giving a pairwise edge-connectivity upper bound of \(2\). No pair has local edge connectivity below \(2\): within either triangle, the two arcs give two edge-disjoint routes; for a cross-pair, the two triangle routes can be joined through \(c\) using distinct edges. Thus every distinct pair has local edge connectivity \(2\), and the global value is \(2\). In particular, it would be incorrect to claim that \(c\) has degree \(2\): its degree is \(4\), so its incident edges do not give the stated two-edge isolation argument.
Worked Example: The Pair Depends on the Parameter
Let \(G=K_{2,3}\), with parts \(X=\{a,b\}\) and \(Y=\{1,2,3\}\), and edge set \(E=\{a1,a2,a3,b1,b2,b3\}\). Find the global parameters and compare pairwise values.
Deleting \(a\) leaves a connected star centered at \(b\), and deleting any one vertex in \(Y\) leaves a connected \(K_{2,2}\). Thus no single vertex deletion disconnects the graph. Deleting both \(a\) and \(b\) leaves three isolated vertices, so \(\kappa(G)=2\). For the pair \(1,2\), the paths \(1,a,2\) and \(1,b,2\) are internally vertex-disjoint. Deleting \(\{a,b\}\) separates \(1\) and \(2\), so \(\kappa_G(1,2)=2\). In contrast, \(a,b\) have three internally vertex-disjoint paths, \(a,1,b\), \(a,2,b\), and \(a,3,b\), so \(\kappa_G(a,b)=3\). The pair attaining the vertex minimum can therefore be chosen from the part of size three, not the part of size two.
Every edge lies on a 4-cycle: for instance, \(a1\) lies on \(a,1,b,2,a\), and the same construction works for each edge by choosing a different vertex in the opposite part. Deleting one edge therefore leaves the graph connected. On the other hand, the two edges incident with vertex \(1\) form an edge cut, so \(\lambda(G)=2\). For \(1,2\), the paths \(1,a,2\) and \(1,b,2\) are edge-disjoint, and the two-edge cut at \(1\) shows \(\lambda_G(1,2)=2\). For \(a,b\), the three paths through \(1,2,3\) are edge-disjoint, giving \(\lambda_G(a,b)\ge3\); the degree of \(a\) is \(3\), so its incident edges give an upper bound of \(3\), and \(\lambda_G(a,b)=3\).
Check: The six listed edges give degrees \(3,3,2,2,2\), whose sum is \(12=2|E|\). The smallest degree is \(2\), matching the two-edge cut isolating any vertex of \(Y\). The pair \(1,2\) witnesses both global minima, while \(a,b\) have larger local values for both parameters.
Worked Example: Two Complete Graphs Sharing an Edge
Let \(G\) have \(V=\{a,b,c,d,e,f\}\) and \(E=\{ab,ac,ad,bc,bd,cd,ae,af,be,bf,ef\}\). Thus the cliques on \(\{a,b,c,d\}\) and \(\{a,b,e,f\}\) share the edge \(ab\). Calculate the global parameters and compare a cross-pair with a pair in one clique.
Deleting \(a,b\) separates \(\{c,d\}\) from \(\{e,f\}\), so \(\kappa(G)\le2\). Deleting no vertices or just one vertex leaves the graph connected: if one of \(a,b\) is deleted, the other still joins the remaining vertices of both cliques; deleting a vertex other than \(a,b\) leaves the shared edge and all remaining vertices connected to it. Hence \(\kappa(G)=2\). The cross-pair \(c,e\) has two internally vertex-disjoint paths \(c,a,e\) and \(c,b,e\). The separator \(\{a,b\}\) bounds its local value by \(2\), so \(\kappa_G(c,e)=2\). For the pair \(c,d\), the paths \(c,d\) and \(c,a,d\) are internally vertex-disjoint, and the same is true of every pair in a clique; the Menger equality stated above ensures no pair has local vertex connectivity below the global minimum.
To calculate the edge connectivity, consider any nontrivial partition of \(V\) into two sides. If the four vertices of \(\{a,b,c,d\}\) are split between the sides, the edges crossing within that \(K_4\) number \(k(4-k)\), where \(k\) is the number on one side. For \(k=1,2,3\), these counts are \(3,4,3\), each at least \(3\). If that clique is not split, then a nontrivial partition must split \(\{a,b,e,f\}\), which contributes at least \(3\) crossing edges by the same calculation. Therefore every edge cut has size at least \(3\). The three edges incident with \(c\), namely \(ac,bc,cd\), isolate \(c\), so \(\lambda(G)=3\). The pair \(c,e\) has three edge-disjoint paths \(c,a,e\), \(c,b,e\), and \(c,d,a,e\) would reuse edge \(ae\), so that proposed third path is invalid. Instead use \(c,d,b,f,e\): its edges \(cd,db,bf,fe\) are distinct from the first two paths. Thus these three paths are edge-disjoint, and the cut isolating \(c\) gives \(\lambda_G(c,e)=3\).
Check: The displayed paths for \(c,e\) use respectively \(\{ca,ae\}\), \(\{cb,be\}\), and \(\{cd,db,bf,fe\}\), with no edge repeated. This verifies the lower bound \(3\) directly; the three-edge cut at \(c\) verifies the upper bound. Here the vertex and edge minima differ: the pair \(c,e\) has local values \(2\) and \(3\), respectively.
Reading the Minima Correctly
The examples show why a global parameter does not identify a unique “weakest pair.” In the two-triangle graph, every pair has local edge connectivity \(2\), while cross-triangle pairs witness the vertex minimum. In \(K_{2,3}\), vertices in the larger part give a pair with local vertex and edge connectivity \(2\), while the pair \(a,b\) has values \(3\). In the graph formed from two \(K_4\) subgraphs, the cross-pair \(c,e\) witnesses the vertex minimum, but its local edge connectivity is larger.
Keep the two kinds of independence separate. Internally vertex-disjoint paths may share edges only when they share endpoints or other vertices permitted by the definition; edge-disjoint paths are controlled by edges and may share internal vertices. A small vertex separator can therefore force a low local vertex value without giving a small edge cut, as the shared-edge clique example demonstrates.
A reliable calculation starts by specifying the graph, then identifies candidate cuts and candidate path families for particular pairs. A cut gives an upper bound; explicit paths give a lower bound. When these bounds agree, the pairwise value is certified. For a general graph, Menger’s theorem guarantees that the minimum pairwise path values agree with the corresponding global cut parameters, but the proof of that theorem is a separate topic.
Check Your Understanding
For each question, state which parameter or pairwise quantity you are using and justify any claimed upper or lower bound.
- In the two-triangle graph, why does deleting the shared vertex give a vertex-connectivity upper bound but not an edge-connectivity upper bound?
- In \(K_{2,3}\), list three internally vertex-disjoint paths between \(a\) and \(b\), and explain why their number does not make \(\kappa(G)=3\).
- In the graph formed from two \(K_4\) subgraphs sharing \(ab\), verify the degrees of \(c\) and \(a\), then give an edge cut of size \(3\) separating \(c\) from the rest.
- Explain why a vertex-separator bound on \(\kappa_G(u,v)\) needs \(u,v\) to be nonadjacent in the proposition above.
- State the local-to-global equalities supplied by Menger’s theorem, and identify which quantity counts paths and which counts deletions.