40.04.04 · combinatorics / graph-theory-core

Connectivity and Menger's Theorem

shipped3 tiersLean: none

Anchor (Master): Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §3.1-§3.5 (the global and directed Menger forms, ear decompositions, Tutte's wheel theorem and the structure of 3-connected graphs, the block-cut tree, and the max-flow link in §6.2); Bondy-Murty 2008 (Springer GTM 244) Ch. 9; Tutte 1966 *Connectivity in Graphs* (University of Toronto Press); the original sources Menger 1927 (the n-arc theorem), Whitney 1932 (κ ≤ λ ≤ δ and 2-connectivity), Tutte 1961 (the wheel theorem)

Intuition Beginner

A network is only as reliable as its weakest bottleneck. If you want to send messages between two cities along a web of cables, the question that matters is not how many cables there are in total, but how many separate, non-overlapping routes you can run at once. Cut a few key cables and the cities go dark; the number you must cut to disconnect them is the true measure of how robustly they are joined.

Graph theory makes this precise with two numbers. The first asks: how few dots can you delete to break the graph into pieces? That count is the connectivity. The second asks the same with lines instead of dots: how few lines must you cut to split it? That is the edge-connectivity. A graph that survives the loss of any single dot is more robust than one with a lone bridge holding it together, and these two numbers rank graphs by exactly that kind of toughness.

The deep surprise, found by Karl Menger in 1927, is that toughness and abundance of routes are the same thing. The fewest dots you need to delete to separate two cities equals the most routes you can draw between them that share no intermediate dot. A bottleneck of size three means three independent routes and no more. This matching of a smallest barrier to a largest bundle of routes is the single most reused idea in all of graph connectivity.

Visual Beginner

Picture two special dots, a source $s$ on the left and a target $t$ on the right, with a tangle of intermediate dots between them. Suppose that no matter how you try to draw routes from $s$ to $t$ that never share a middle dot, you can manage at most three such routes before you run out of room. Menger's theorem promises that, somewhere in the tangle, there are exactly three middle dots whose removal cuts every possible $s$ -to- $t$ route at once.

The table records the three routes and marks, for each, the one separating dot it must pass through. Three routes, three cut dots, and they line up one-to-one. That pairing is the visual content of the theorem: a smallest wall always has exactly as many bricks as the largest bundle of routes it blocks.

route	passes through cut dot
top route	dot $a$
middle route	dot $b$
bottom route	dot $c$
a fourth route?	impossible

The fourth row is the point. Once three dots wall off $s$ from $t$ , no fourth independent route can exist, because any route must cross the wall, and the wall has only three bricks to land on.

Worked example Beginner

Take a concrete small network and find both its bottleneck and its bundle of routes by hand. Use the graph on six dots $s, a, b, c, d, t$ with lines $s - a$ , $s - b$ , $a - c$ , $b - d$ , $c - t$ , $d - t$ , and one extra cross line $a - d$ . We want the most routes from $s$ to $t$ that share no middle dot.

Step 1. Find one route. Start $s, a, c, t$ . That uses middle dots $a$ and $c$ .

Step 2. Find a second route avoiding those middle dots. Try $s, b, d, t$ , using middle dots $b$ and $d$ . It shares no middle dot with the first, so we now have two independent routes.

Step 3. Try for a third route. Every remaining way out of $s$ uses either $a$ or $b$ , and both are already taken. The cross line $a - d$ does not help, because reaching $d$ that way still passes through $a$ , already used. So two routes is the most we can draw.

Step 4. Find the matching bottleneck. Delete the two dots $a$ and $b$ . Now $s$ has no lines left at all, so $s$ is cut off from $t$ . Two deleted dots disconnect the network.

What this tells us: the largest bundle of independent routes (two) exactly equals the smallest number of middle dots whose deletion separates $s$ from $t$ (two). We did not have to trust a theorem to see it here — we found both numbers directly and watched them agree. That agreement, holding for every graph and every pair of dots, is Menger's theorem.

Check your understanding Beginner

Formal definition Intermediate+

Throughout, $G = (V, E)$ is a finite graph with $n = ∣ V ∣ \geq 2$ . A separator (or vertex cut) for two non-adjacent vertices $s, t$ is a set $S \subseteq V ∖ {s, t}$ such that $G - S$ has no $s$ – $t$ path. More generally a set $S \subseteq V$ is a vertex cut of $G$ if $G - S$ is disconnected or has fewer than two vertices. The (vertex-)connectivity is $$ \kappa(G) = \min{ |S| : S \subseteq V,\ G - S \text{ is disconnected or has } \leq 1 \text{ vertex} }, $$ with the convention $κ (K_{n}) = n - 1$ for the complete graph (which no vertex deletion disconnects). $G$ is $k$ -connected if $n > k$ and $κ (G) \geq k$ — equivalently, $G$ remains connected after deleting any fewer than $k$ vertices ^{[Diestel 2017 §3.1]}. The $1$ -connected graphs are the connected graphs on $\geq 2$ vertices; the $2$ -connected graphs are the connected graphs with no cutvertex (a vertex whose deletion disconnects the graph).

An edge cut separating $s$ from $t$ is a set $F \subseteq E$ such that $G - F$ has no $s$ – $t$ path. The edge-connectivity is $$ \lambda(G) = \min{ |F| : F \subseteq E,\ G - F \text{ is disconnected} }, $$ for $n \geq 2$ , and $λ (G) = 0$ if $G$ is already disconnected. $G$ is $k$ -edge-connected if $λ (G) \geq k$ . A single edge whose removal disconnects $G$ is a bridge; $λ (G) \geq 2$ means $G$ is bridgeless.

Two $s$ – $t$ paths are internally disjoint (or independent) if they share no vertex other than $s$ and $t$ ; they are edge-disjoint if they share no edge. Write $κ_{G} (s, t)$ for the maximum number of pairwise internally disjoint $s$ – $t$ paths and $λ_{G} (s, t)$ for the maximum number of pairwise edge-disjoint $s$ – $t$ paths. The local vertex-separator number $σ_{G} (s, t)$ is the minimum size of an $s$ – $t$ separator (for non-adjacent $s, t$ ), and the local edge-cut number is the minimum size of an $s$ – $t$ edge cut.

A maximal connected subgraph with no cutvertex of its own is a block: a block is either a maximal $2$ -connected subgraph, a bridge with its two endpoints, or an isolated vertex. The blocks and cutvertices of $G$ assemble into the block-cut tree $T (G)$ , the bipartite graph whose vertices are the blocks and the cutvertices, with a block $B$ joined to a cutvertex $v$ exactly when $v \in B$ .

Counterexamples to common slips

Connectivity is not edge-connectivity. The graph consisting of two triangles sharing a single vertex has $κ = 1$ (delete the shared vertex) but $λ = 2$ (no single edge disconnects it). The two invariants coincide on many graphs but diverge exactly at cutvertices that are not bridges.
$κ (G) \geq k$ requires $n > k$ . The complete graph $K_{k}$ has $κ = k - 1 < k$ , so $K_{k}$ is $(k - 1)$ -connected but not $k$ -connected; the convention $κ (K_{n}) = n - 1$ keeps the inequality $κ \leq n - 1$ tight rather than letting $K_{n}$ be "infinitely connected".
Menger's separator must avoid the endpoints. For adjacent $s, t$ no vertex set separates them, so the local vertex form is stated for non-adjacent pairs; the edge form and the global form have no such restriction, which is one reason the edge form is often the cleaner statement.
A block need not be $2$ -connected. A bridge together with its two endpoints is a block (a maximal subgraph with no cutvertex of its own), even though it is not $2$ -connected; the block decomposition mixes $2$ -connected blocks with bridge-blocks and isolated vertices.

Key theorem with proof Intermediate+

Theorem (Whitney's inequality and Menger's theorem, local vertex form). Let $G$ be a graph with $n \geq 2$ vertices.

(a) Whitney's inequality. $κ (G) \leq λ (G) \leq δ (G)$ , where $δ (G)$ is the minimum degree.

(b) Menger, local vertex form. For non-adjacent vertices $s, t$ , the maximum number $κ_{G} (s, t)$ of internally disjoint $s$ – $t$ paths equals the minimum size $σ_{G} (s, t)$ of an $s$ – $t$ separator.

(See ^{[Diestel 2017 §3.3]}, ^{[Whitney 1932]}, ^{[Menger 1927]}.)

Proof. Part (a). For $λ \leq δ$ : pick a vertex $v$ of minimum degree $δ$ ; deleting its $δ$ incident edges isolates $v$ , so a $δ$ -element edge cut exists and $λ \leq δ$ . For $κ \leq λ$ : take a minimum edge cut $F$ with $∣ F ∣ = λ$ splitting $V$ into $X$ and $Y$ . If every vertex of $X$ is joined to every vertex of $Y$ then $λ = ∣ X ∣∣ Y ∣ \geq n - 1 \geq κ$ . Otherwise pick $x \in X$ , $y \in Y$ non-adjacent, and for each edge of $F$ choose an endpoint, taking the $X$ -endpoint unless that endpoint is $x$ , in which case take the $Y$ -endpoint. This selects at most $λ$ vertices, none equal to $x$ or $y$ , and deleting them destroys every $x$ – $y$ path (each such path crosses $F$ , hence meets a chosen vertex). So $κ \leq λ$ .

Part (b). The inequality $κ_{G} (s, t) \leq σ_{G} (s, t)$ is immediate: each separator must contain an internal vertex of each of the disjoint paths, and these internal vertices are distinct, so a separator has at least $κ_{G} (s, t)$ vertices. The content is the reverse, $κ_{G} (s, t) \geq σ_{G} (s, t)$ , proved by induction on $∣ E (G) ∣$ . Write $k = σ_{G} (s, t)$ ; we produce $k$ internally disjoint $s$ – $t$ paths.

If $G$ has no edge, $k = 0$ and there is nothing to prove. Otherwise pick an edge $e = {x, y}$ with $x, y \in / {s, t}$ if one exists; we treat the generic case and indicate the boundary cases after. Consider $G / e$ , the contraction of $e$ to a single vertex $v_{e}$ . Any $s$ – $t$ separator $S^{'}$ of $G / e$ of size $< k$ lifts to an $s$ – $t$ separator of $G$ of size $\leq ∣ S^{'} ∣ + 1 \leq k$ (replace $v_{e}$ by ${x, y}$ if $v_{e} \in S^{'}$ ), and a careful choice shows it can be taken of size $< k$ unless every minimum separator of $G$ uses both $x$ and $y$ .

So either $σ_{G / e} (s, t) \geq k$ , and induction (fewer edges) gives $k$ disjoint paths in $G / e$ that pull back to $k$ in $G$ ; or there is a separator $S$ of $G$ of size $k$ containing both $x$ and $y$ . In the latter case set $S$ as a minimum separator with ${x, y} \subseteq S$ . The graph $G_{s}$ obtained from $G$ by keeping the $s$ -side of $S$ together with $S$ (adding a new vertex $t^{'}$ joined to all of $S$ ) has fewer edges, and in it $S$ is again a minimum $s$ – $t^{'}$ separator of size $k$ , so induction yields $k$ disjoint $s$ – $S$ paths meeting $S$ in distinct vertices; symmetrically $k$ disjoint $S$ – $t$ paths. Splicing each $s$ – $S$ path to the $S$ – $t$ path through the same vertex of $S$ produces $k$ internally disjoint $s$ – $t$ paths. Finally, if every edge is incident to $s$ or $t$ , then deleting the neighbours of $s$ (other than $t$ , which is non-adjacent) gives a separator, and a direct matching argument on the neighbourhoods produces $k$ length- $\leq 2$ paths. In all cases $κ_{G} (s, t) \geq k = σ_{G} (s, t)$ . $□$

Bridge. This theorem builds toward every later connectivity and flow result and appears again in the global form, the fan lemma, the ear decompositions, and the max-flow-min-cut theorem, because all of them are this same min-max identity read on different objects. The foundational reason Whitney's chain $κ \leq λ \leq δ$ and Menger's equality sit together is that both convert a deletion question into a routing question: $λ \leq δ$ is the edge-cut at a minimum-degree vertex, and Menger is exactly the statement that no smaller wall than the largest route-bundle can exist. This is exactly the principle that a minimum separator is a certificate of optimality for a maximum disjoint-path family — the wall and the bundle certify each other's size. The vertex form generalises to the edge form by the standard line-graph or vertex-splitting reduction, and the local form generalises to the global form by quantifying over all pairs, so the single induction above is the engine of the whole chapter. Putting these together, the bridge is that Menger's theorem is the integral max-flow-min-cut theorem with all capacities equal to one, which is why the connectivity numbers of this unit are computed in practice by network-flow algorithms.

Exercises Intermediate+

Exercise 4 (medium, short-answer).

State and prove the edge form of Menger's theorem from the vertex form: for any (possibly adjacent) $s, t$ , the maximum number of edge-disjoint $s$ – $t$ paths equals the minimum size of an $s$ – $t$ edge cut.

Hint

Apply the vertex form to the line graph, or split each vertex into an in-copy and an out-copy joined by an edge.

Answer

Edge-disjoint $s$ – $t$ paths in $G$ correspond to internally disjoint $s$ – $t$ paths in a derived graph $H$ obtained by subdividing or by passing to a suitable vertex-split. One clean route: form $H$ on the edge set, joining two edges if they share an endpoint (the line graph $L (G)$ ), with auxiliary terminals for the edges at $s$ and at $t$ ; internally disjoint paths in this structure are edge-disjoint paths in $G$ , and a vertex separator in $H$ is an edge cut in $G$ . Applying the vertex form gives max edge-disjoint paths $=$ min edge cut. (Equivalently, replace each vertex $v$ by $v_{in} \to v_{out}$ ; vertex-disjointness in the split graph is edge-disjointness in $G$ .) Rubric: full credit for a correct reduction (line graph or vertex split) plus the citation of the vertex form.

Exercise 5 (medium, short-answer).

Prove the fan lemma: if $G$ is $k$ -connected, $v$ is a vertex, and $U$ is a set of $k$ vertices not containing $v$ , then there exist $k$ paths from $v$ to $U$ that are pairwise disjoint except at $v$ and each meet $U$ only in its endpoint (a $v$ – $U$ fan).

Hint

Add a new vertex $u^{*}$ adjacent to all of $U$ and apply Menger between $v$ and $u^{*}$ .

Answer

Form $G^{+}$ by adding a new vertex $u^{*}$ joined to every vertex of $U$ . In $G^{+}$ any $v$ – $u^{*}$ separator $S$ avoiding $v, u^{*}$ must separate $v$ from $U$ in $G$ , so $∣ S ∣ \geq k$ (else $S$ would be a $< k$ -separator of the $k$ -connected $G$ , since $∣ U ∣ = k$ forces $S$ to block all of $U$ ). Hence the minimum $v$ – $u^{*}$ separator has size $\geq k$ , and by Menger there are $k$ internally disjoint $v$ – $u^{*}$ paths. Deleting the final vertex $u^{*}$ from each leaves $k$ paths from $v$ to distinct vertices of $U$ , pairwise disjoint except at $v$ : a $v$ – $U$ fan. Rubric: full credit for the $u^{*}$ construction and the Menger application.

Exercise 7 (hard, short-answer).

Prove the global vertex form of Menger's theorem: a graph $G$ with $n > k$ vertices is $k$ -connected if and only if every pair of distinct vertices is joined by $k$ internally disjoint paths.

Hint

For non-adjacent pairs use the local form directly. For adjacent pairs $s, t$ , delete the edge $s t$ and argue in $G - s t$ , then re-attach.

Answer

( $\Leftarrow$ ) If every pair is joined by $k$ internally disjoint paths, then no set of $< k$ vertices can separate any pair (each separator meets each of the $k$ disjoint paths in a distinct internal vertex), so $κ (G) \geq k$ . ( $\Rightarrow$ ) Suppose $κ (G) \geq k$ and take vertices $s \neq = t$ . If $s, t$ are non-adjacent, every separator has $\geq k$ vertices (a $< k$ separator would contradict $k$ -connectivity), so by the local form there are $k$ internally disjoint $s$ – $t$ paths. If $s \sim t$ , consider $G^{'} = G - s t$ . The edge $s t$ is one path; we need $k - 1$ more internally disjoint paths in $G^{'}$ avoiding the edge. One checks $G^{'}$ has the property that the minimum $s$ – $t$ separator (now $s, t$ may be non-adjacent in $G^{'}$ ) has size $\geq k - 1$ : deleting fewer than $k - 1$ vertices from $G^{'}$ leaves $s, t$ joined, because deleting them from $G$ left $s, t$ in a common component of size $\geq 2$ that the single edge $s t$ did not solely sustain (here $n > k$ guarantees room). By the local form $G^{'}$ has $k - 1$ internally disjoint $s$ – $t$ paths; together with the edge $s t$ these give $k$ internally disjoint $s$ – $t$ paths in $G$ . Rubric: full credit for the non-adjacent case via the local form and the edge-deletion argument for the adjacent case.

Exercise 8 (hard, short-answer).

Prove that a graph $G$ on at least $3$ vertices is $2$ -connected if and only if it can be built from a cycle by successively adding ears (paths whose two endpoints are old vertices and whose interior is new); this is the open-ear decomposition.

Hint

For "if", show each ear addition preserves $2$ -connectivity. For "only if", grow a maximal $2$ -connected ear-built subgraph and use a $v$ –path to extend it.

Answer

( $\Leftarrow$ ) A cycle is $2$ -connected. Adding an ear $P$ to a $2$ -connected $H$ keeps it $2$ -connected: any single vertex deletion leaves $H$ connected (if the deleted vertex lies in $H$ ) and the ear interior is attached at two points, so no cutvertex is created. Induction gives $2$ -connectivity. ( $\Rightarrow$ ) Let $G$ be $2$ -connected. It contains a cycle (a $2$ -connected graph has minimum degree $\geq 2$ , forcing a cycle). Let $H \subseteq G$ be a maximal subgraph obtainable by ear additions starting from a cycle. If $H \neq = G$ , then since $G$ is connected there is an edge $e = x y$ with $x \in H$ , and since $G$ is $2$ -connected $G - x$ is connected, giving a path from $y$ back to a second vertex of $H$ avoiding $x$ ; that path (with $e$ ) is an ear, so $H + ear ⊊ G$ extends $H$ , contradicting maximality. If $H = G$ but some edge of $G$ is missing from $H$ , that edge is itself a length- $1$ ear between two $H$ -vertices, again extending $H$ . So $H = G$ and $G$ has an open-ear decomposition. Rubric: full credit for the ear-addition preservation and the maximality extension argument.

Advanced results Master

Theorem (Menger, global edge form, and the flow identity). For all $s \neq = t$ , the maximum number of edge-disjoint $s$ – $t$ paths equals the minimum size of an $s$ – $t$ edge cut, and $G$ is $k$ -edge-connected iff every pair is joined by $k$ edge-disjoint paths. Assigning every edge capacity $1$ , this minimum cut equals the integral maximum $s$ – $t$ flow. (Diestel ^{[Diestel 2017 §3.3, §6.2]}; Bondy-Murty ^{[Bondy-Murty 2008 Ch. 9]}.) The vertex form reduces to the edge form by the vertex-split $v \mapsto (v_{in} \to v_{out})$ with the internal edge carrying capacity $1$ , so internally disjoint paths in $G$ become edge-disjoint paths in the split graph and separators become unit cuts; conversely the edge form is the vertex form on the line graph. The max-flow-min-cut theorem, proved by an augmenting-path argument, has integral optimal flow when capacities are integral, and a unit-capacity integral flow of value $k$ decomposes into $k$ edge-disjoint paths. Menger's theorem is therefore the unit-capacity special case of max-flow-min-cut, and the connectivities $κ (G), λ (G)$ are computed by $(2 n)$ flow computations (or fewer, by Gomory-Hu and Even-Tarjan refinements).

Theorem (the directed form). In a digraph $D$ , for vertices $s \neq = t$ the maximum number of arc-disjoint directed $s$ – $t$ paths equals the minimum number of arcs whose deletion destroys all directed $s$ – $t$ paths; likewise for internally-disjoint directed paths and directed vertex separators. (Menger ^{[Menger 1927]}; Diestel ^{[Diestel 2017 §3.3]}.) The directed edge form is again unit-capacity max-flow-min-cut on the digraph, and the undirected forms follow by replacing each edge with two opposed arcs. The directed vertex form, due in this packaging to the same flow argument with vertex-splitting, underlies disjoint-path routing and the Lucchesi-Younger and Nash-Williams orientation theorems.

Theorem (Tutte's wheel theorem; structure of $3$ -connected graphs). Every $3$ -connected graph $G$ on $\geq 5$ vertices has an edge $e$ such that $G / e$ or $G - e$ is again $3$ -connected; consequently every $3$ -connected graph can be reduced to a wheel $W_{k}$ by a sequence of edge contractions and deletions through $3$ -connected graphs, and dually every $3$ -connected graph is obtained from a wheel by vertex-splittings and edge-additions. (Tutte ^{[Tutte 1961]}; Diestel ^{[Diestel 2017 §3.2]}.) The wheel $W_{k}$ — a cycle $C_{k}$ plus a hub joined to all rim vertices — is the minimal $3$ -connected building block, and the theorem realises the $3$ -connected graphs as exactly the closure of the wheels under the two operations. This is the connectivity analogue of the ear decomposition one dimension up: where $2$ -connected graphs grow from a cycle by ears, $3$ -connected graphs grow from a wheel by splits, and the theorem is the structural pinnacle of low-order connectivity, feeding directly into the uniqueness of planar embeddings (a $3$ -connected planar graph has an essentially unique embedding, by Whitney) and into the SPQR-tree decomposition used in graph drawing.

Theorem (block decomposition and the block-cut tree). Every connected graph $G$ decomposes uniquely into blocks (maximal subgraphs without a cutvertex), any two blocks share at most one vertex, that shared vertex is a cutvertex of $G$ , and the block-cut incidence graph $T (G)$ is a tree. (Diestel ^{[Diestel 2017 §3.1]}; Bondy-Murty ^{[Bondy-Murty 2008 Ch. 5, 9]}.) The relation "lie on a common cycle or are joined by an edge" is an equivalence on the edges of $G$ whose classes are the blocks; two blocks meeting in two vertices would merge into one larger block (the two shared vertices, together with internally disjoint paths through each block, form a cycle straddling both), so blocks overlap in at most a single cutvertex. The bipartite block-cut graph is connected (since $G$ is) and acyclic (a cycle in $T (G)$ would force two blocks to share two cutvertices), hence a tree — the coarse skeleton on which higher connectivity is then analysed block by block.

Synthesis. Putting these together, the entire connectivity chapter is one min-max identity — Menger's — instantiated at every level and certified by the max-flow-min-cut theorem. The central insight is that a minimum separator and a maximum disjoint-path family certify each other's size, and this is exactly the principle that the vertex form, the edge form, the directed form, and the global form are four readings of the unit-capacity flow value; the bridge is the vertex-split that turns internally-disjoint vertex routing into edge routing, so a single flow computation answers all of them. The foundational reason the structural theorems stack — ear decomposition for $κ \geq 2$ , the wheel theorem for $κ \geq 3$ , the block-cut tree for the general connected graph — is that each builds the graph from an irreducible core (a cycle, a wheel, a single block) by connectivity-preserving moves, so connectivity is generated, not merely measured.

The ear decomposition is dual to the block tree: ears assemble a single $2$ -connected block from a cycle, while the block tree assembles the whole graph from its blocks, and Whitney's $κ \leq λ \leq δ$ is the numerical spine threading both, since the minimum-degree vertex bounds the edge-connectivity that bounds the vertex-connectivity that the ear and wheel constructions then realise. This generalises the foundational handshake-and-tree machinery of the root unit: where trees were the minimal connected skeletons, blocks and ears are the minimal $2$ - and $3$ -connected ones, and the flow identity is the quantitative engine that the planarity and network-flow units inherit wholesale.

Full proof set Master

Proposition 1 (Whitney's inequality). For every graph $G$ with $\geq 2$ vertices, $κ (G) \leq λ (G) \leq δ (G)$ .

Proof. For $λ \leq δ$ , let $v$ attain the minimum degree $δ$ . The $δ$ edges incident to $v$ form an edge cut separating $v$ from the rest, so $λ \leq δ$ . For $κ \leq λ$ , take a minimum edge cut $F$ , $∣ F ∣ = λ$ , with vertex bipartition $V = X ⊔ Y$ so that $F$ is the set of $X$ – $Y$ edges. If every $X$ - $Y$ pair is adjacent, $λ = ∣ X ∣ ∣ Y ∣ \geq ∣ X ∣ + ∣ Y ∣ - 1 = n - 1 \geq κ$ . Otherwise fix non-adjacent $x \in X$ , $y \in Y$ . For each edge of $F$ select its $X$ -endpoint, except when that endpoint is $x$ , in which case select its $Y$ -endpoint (which is not $y$ , as $x \neq \sim y$ ). The selected set $S$ has $∣ S ∣ \leq λ$ , omits $x$ and $y$ , and meets every $x$ – $y$ path (each crosses an edge of $F$ and thus contains a selected endpoint). So $S$ separates $x$ from $y$ and $κ \leq ∣ S ∣ \leq λ$ . $□$

Proposition 2 (Menger, local vertex form). For non-adjacent $s, t$ , $κ_{G} (s, t) = σ_{G} (s, t)$ .

Proof. The bound $κ_{G} (s, t) \leq σ_{G} (s, t)$ holds because a separator contains a distinct internal vertex from each disjoint path. For the reverse, induct on $∣ E ∣$ with $k = σ_{G} (s, t)$ . If $∣ E ∣ = 0$ then $k = 0$ . Otherwise pick an edge $e = x y$ . Suppose first $σ_{G / e} (s, t) \geq k$ (with $s, t \neq = v_{e}$ , treating $x, y \in / {s, t}$ ): by induction $G / e$ has $k$ internally disjoint $s$ – $t$ paths, and expanding $v_{e}$ back to the edge $x y$ yields $k$ internally disjoint paths in $G$ . Otherwise $G / e$ has a separator of size $< k$ ; lifting it shows $G$ has a minimum separator $S$ , $∣ S ∣ = k$ , with $x, y \in S$ . Let $V_{s}$ be the vertices reachable from $s$ in $G - S$ , together with $S$ ; form $G_{s}$ on $V_{s} \cup {t^{*}}$ with $t^{*}$ adjacent to all of $S$ . Then $σ_{G_{s}} (s, t^{*}) = k$ and $G_{s}$ has fewer edges (it omits the entire $t$ -side, which is non-empty since $S$ separates), so by induction $G_{s}$ has $k$ disjoint $s$ – $t^{*}$ paths, i.e. $k$ disjoint $s$ – $S$ paths ending in the $k$ distinct vertices of $S$ . Symmetrically $G_{t}$ gives $k$ disjoint $S$ – $t$ paths. Concatenating through the common vertices of $S$ produces $k$ internally disjoint $s$ – $t$ paths in $G$ . The boundary case in which every edge meets ${s, t}$ reduces to a bipartite matching between $N (s)$ and $N (t)$ , again of size $k$ by König's theorem. Hence $κ_{G} (s, t) = k$ . $□$

Proposition 3 (global vertex form). A graph on $n > k$ vertices is $k$ -connected iff every pair of vertices is joined by $k$ internally disjoint paths.

Proof. If every pair has $k$ internally disjoint paths, no $(k - 1)$ -set separates any pair, so $κ \geq k$ . Conversely let $κ (G) \geq k$ and $s \neq = t$ . For non-adjacent $s, t$ every separator has $\geq k$ vertices, so Proposition 2 gives $k$ internally disjoint paths. For adjacent $s, t$ , apply the local form in $G - s t$ : the minimum $s$ – $t$ separator there has size $\geq k - 1$ (deleting $\leq k - 2$ vertices keeps $s, t$ joined in $G$ by $> 1$ path, one surviving in $G - s t$ , using $n > k$ ), giving $k - 1$ internally disjoint paths in $G - s t$ , which with the edge $s t$ make $k$ in $G$ . $□$

Proposition 4 (fan lemma). If $G$ is $k$ -connected, $v \in V$ , and $U \subseteq V ∖ {v}$ with $∣ U ∣ = k$ , there is a $v$ – $U$ fan of $k$ paths, disjoint except at $v$ , each meeting $U$ only at its end.

Proof. Add $u^{*}$ adjacent to all of $U$ , forming $G^{+}$ . A $v$ – $u^{*}$ separator $S$ (with $v, u^{*} \in / S$ ) separates $v$ from $U$ in $G$ ; since $∣ U ∣ = k$ and deleting $S$ must block every $v$ – $U$ path, $S$ is a $v$ -to- $U$ separator in the $k$ -connected $G$ , so $∣ S ∣ \geq k$ . By Proposition 2, $G^{+}$ has $k$ internally disjoint $v$ – $u^{*}$ paths; removing $u^{*}$ from each leaves $k$ paths from $v$ to distinct vertices of $U$ , disjoint except at $v$ — a $v$ – $U$ fan. $□$

Proposition 5 (open-ear decomposition). A graph on $\geq 3$ vertices is $2$ -connected iff it admits an open-ear decomposition starting from a cycle.

Proof. ( $\Leftarrow$ ) A cycle is $2$ -connected; adding an open ear $P$ (interior new, endpoints distinct old vertices) to a $2$ -connected $H$ preserves $2$ -connectivity, since deleting one vertex of $H$ keeps $H$ connected and the ear is attached at two points, while deleting an interior ear vertex leaves $H$ and the ear remainder connected through the two attachment points. Induction gives the result. ( $\Rightarrow$ ) Let $G$ be $2$ -connected, hence $δ (G) \geq 2$ , so $G$ contains a cycle $C$ . Take a maximal $H \subseteq G$ built from $C$ by open ears. If $H \neq = G$ : by connectivity some edge $e = x y$ has $x \in H$ , $y \in / H$ (or $x, y \in H$ with $e \in / H$ , a length- $1$ ear, extending $H$ ). For $y \in / H$ , since $G - x$ is connected ( $G$ is $2$ -connected) there is a $y$ – $H$ path $P$ in $G - x$ ending at a vertex $z \in H$ with $z \neq = x$ ; then $x ey P z$ is an open ear with both ends in $H$ and new interior, so $H$ extends — contradiction. Hence $H = G$ . $□$

Proposition 6 (block-cut tree is a tree). The blocks of a connected graph $G$ , with two blocks adjacent to a shared cutvertex, form a tree $T (G)$ ; any two blocks meet in at most one vertex, which is a cutvertex.

Proof. Define a relation on edges: $e \sim f$ if $e = f$ or $e, f$ lie on a common cycle. This is an equivalence (transitivity uses that two cycles sharing an edge combine into a cycle through any third edge of either), and its classes, with their incident vertices, are the blocks. Two blocks $B_{1}, B_{2}$ sharing two vertices $u, w$ would have internally disjoint $u$ – $w$ paths in each (each block is $2$ -connected or a single edge), forming a cycle spanning both, forcing $B_{1}, B_{2}$ into one class — contradiction; so they share at most one vertex, necessarily a cutvertex. The block-cut graph is connected because $G$ is, and acyclic: a cycle in $T (G)$ would be an alternating block-cutvertex sequence $B_{1} c_{1} B_{2} c_{2} \dots B_{1}$ with distinct $c_{i}$ , but then $B_{1}, \dots, B_{m}$ would lie on a common cycle in $G$ and hence form a single block. A connected acyclic graph is a tree. $□$

Connections Master

Graphs, basic invariants, and the foundational lemmas 40.04.01. Connectivity refines the root chapter's notion of "connected" into a graded scale: where that unit established components, trees, and the handshake count, this unit measures how robustly a graph holds together and proves the min-max law governing it. Whitney's $κ \leq λ \leq δ$ ties the new invariants directly to the minimum degree defined there, the spanning-tree existence used in the block decomposition is the root unit's Proposition 2, and the ear and wheel decompositions are the connectivity-graded successors of the tree as a minimal skeleton.
Planar graphs and Kuratowski-Wagner 40.04.05. Three-connectivity is the hinge of planarity: Whitney's theorem says a $3$ -connected planar graph has an essentially unique embedding in the sphere, and Tutte's wheel theorem supplies the induction that builds every $3$ -connected graph from a wheel — the scaffold on which planarity proofs proceed. The planarity unit imports the wheel theorem and the structure of $3$ -connected graphs proved here, and Menger's theorem provides the disjoint paths used in the standard proof that subdivisions of $K_{5}$ or $K_{3, 3}$ obstruct embedding.
Network flows and max-flow-min-cut 40.04.09. Menger's theorem is the integral, unit-capacity case of the max-flow-min-cut theorem: edge-disjoint paths are an integral flow and a minimum edge cut is a minimum capacity cut. The flows unit develops the augmenting-path and capacity-scaling algorithms that compute $κ (G)$ and $λ (G)$ , generalises the directed form proved here to arbitrary capacities, and carries the Gomory-Hu and Menger-Whitney duality into the full theory of cuts; the connectivity numbers of this unit are exactly the quantities those algorithms output.

Historical & philosophical context Master

The min-max identity at the centre of this unit was proved by Karl Menger in 1927, in Zur allgemeinen Kurventheorie (Fundamenta Mathematicae 10) ^{[Menger 1927]}, as a lemma in his work on the dimension and structure of curves: his " $n$ -arc theorem" stated that the minimum number of points separating two sets equals the maximum number of disjoint arcs joining them. The graph-theoretic reading — disjoint paths versus separating vertices — was made explicit shortly afterward, and the equivalence with the edge form and with what would become the max-flow-min-cut theorem of Ford and Fulkerson (1956) and Elias-Feinstein-Shannon (1956) was recognised as the same duality in different clothing. Hassler Whitney, in his 1932 Congruent graphs and the connectivity of graphs (American Journal of Mathematics 54) ^{[Whitney 1932]}, introduced the connectivity number, proved the inequality $κ \leq λ \leq δ$ , and gave the cycle characterisation of $2$ -connectivity that underlies the ear decomposition.

The structure theory of higher connectivity is due to William Tutte, whose 1961 A theory of $3$ -connected graphs (Indagationes Mathematicae 23) ^{[Tutte 1961]} proved the wheel theorem and established the wheels as the irreducible $3$ -connected graphs; his 1966 monograph Connectivity in Graphs (University of Toronto Press) consolidated the field. Robert Hopcroft and John Tarjan's 1973 linear-time algorithms for finding biconnected and triconnected components turned the block-cut tree and the SPQR decomposition into computational tools. The textbook organisation followed in Reinhard Diestel's Graph Theory ^{[Diestel 2017]}, whose third chapter presents the connectivity numbers, Menger's theorem in all its forms, the ear and wheel decompositions, and the link to flows as a single connected development.

Bibliography Master

@book{Diestel2017,
  author    = {Diestel, Reinhard},
  title     = {Graph Theory},
  edition   = {5th},
  series    = {Graduate Texts in Mathematics},
  volume    = {173},
  publisher = {Springer},
  year      = {2017}
}

@book{BondyMurty2008,
  author    = {Bondy, J. A. and Murty, U. S. R.},
  title     = {Graph Theory},
  series    = {Graduate Texts in Mathematics},
  volume    = {244},
  publisher = {Springer},
  year      = {2008}
}

@article{Menger1927,
  author  = {Menger, Karl},
  title   = {Zur allgemeinen Kurventheorie},
  journal = {Fundamenta Mathematicae},
  volume  = {10},
  year    = {1927},
  pages   = {96--115}
}

@article{Whitney1932,
  author  = {Whitney, Hassler},
  title   = {Congruent graphs and the connectivity of graphs},
  journal = {American Journal of Mathematics},
  volume  = {54},
  number  = {1},
  year    = {1932},
  pages   = {150--168}
}

@article{Tutte1961,
  author  = {Tutte, William T.},
  title   = {A theory of 3-connected graphs},
  journal = {Indagationes Mathematicae},
  volume  = {23},
  year    = {1961},
  pages   = {441--455}
}

@book{Tutte1966,
  author    = {Tutte, William T.},
  title     = {Connectivity in Graphs},
  publisher = {University of Toronto Press},
  year      = {1966}
}

@article{FordFulkerson1956,
  author  = {Ford, L. R. and Fulkerson, D. R.},
  title   = {Maximal flow through a network},
  journal = {Canadian Journal of Mathematics},
  volume  = {8},
  year    = {1956},
  pages   = {399--404}
}

@article{HopcroftTarjan1973,
  author  = {Hopcroft, John E. and Tarjan, Robert E.},
  title   = {Dividing a graph into triconnected components},
  journal = {SIAM Journal on Computing},
  volume  = {2},
  number  = {3},
  year    = {1973},
  pages   = {135--158}
}

Prerequisites

40.04.01

Tier anchors

beginner: Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §3.1-§3.2 read for the pictures of cuts and disjoint paths; West 2001 *Introduction to Graph Theory* (2nd ed., Prentice Hall) §4.1-§4.2 for the dots-and-lines vocabulary of vertex cuts and the fan picture; 3Blue1Brown's network-flow and bottleneck essays for the max-paths-equals-min-cut intuition
intermediate: Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §3.1-§3.3 (the connectivities κ and λ, Whitney's inequality, Menger's theorem in vertex/edge/global form, the fan lemma, 2-connected graphs and ear decompositions); Bondy-Murty 2008 *Graph Theory* (Springer GTM 244) Ch. 9 (connectivity, Menger, Whitney)
master: Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §3.1-§3.5 (the global and directed Menger forms, ear decompositions, Tutte's wheel theorem and the structure of 3-connected graphs, the block-cut tree, and the max-flow link in §6.2); Bondy-Murty 2008 (Springer GTM 244) Ch. 9; Tutte 1966 *Connectivity in Graphs* (University of Toronto Press); the original sources Menger 1927 (the n-arc theorem), Whitney 1932 (κ ≤ λ ≤ δ and 2-connectivity), Tutte 1961 (the wheel theorem)

References

Diestel 2017 — Graph Theory (5th edition) · Springer Graduate Texts in Mathematics 173, 2017, Ch. 3 (§3.1 2-connected graphs and ear decomposition; §3.2 the structure of 3-connected graphs and Tutte's wheel theorem; §3.3 Menger's theorem in its vertex, edge, and global forms with the fan lemma; §3.4 Mader's theorem; §3.5 linking pairs of vertices)
Bondy, Murty 2008 — Graph Theory · Springer Graduate Texts in Mathematics 244, 2008, Ch. 9 (connectivity, vertex and edge connectivity, Whitney's inequality, Menger's theorem, ear decompositions, the block tree)
Menger 1927 — Zur allgemeinen Kurventheorie · Fundamenta Mathematicae 10 (1927) 96-115; the n-arc theorem equating the minimum size of a separating set with the maximum number of disjoint connecting arcs
Whitney 1932 — Congruent graphs and the connectivity of graphs · American Journal of Mathematics 54 (1932) 150-168; the inequality κ(G) ≤ λ(G) ≤ δ(G) and the cycle characterisation of 2-connectivity
Tutte 1961 — A theory of 3-connected graphs · Indagationes Mathematicae 23 (1961) 441-455; the wheel theorem, that every 3-connected graph reduces to a wheel by edge deletions and contractions preserving 3-connectivity

Estimated time

beginner: 20m
intermediate: 50m
master: 90m