Menger theorem

The maximum number of disjoint paths joining two vertex sets equals the minimum size of a separating set, with vertex and edge versions according to the chosen notion of disjointness.

Graph paths are vertex-disjoint if no vertex belongs to more than one of them, including their endpoints. In contrast, internally vertex-disjoint paths between common endpoints are allowed to share exactly those endpoints. The Set version of Menger theorem uses vertex-disjointness, while the two-terminal form uses internal vertex-disjointness.

An $x$-$y$ vertex separator is a set of vertices, excluding $x$ and $y$, whose deletion leaves no path from $x$ to $y$.

For nonadjacent vertices $a,b$ of a graph $G$, their local connectivity $\kappa (a,b;G)$ is the minimum size of an $a$-$b$ vertex separator. By the Menger theorem, it also equals the maximum number of internally vertex-disjoint $a$-$b$ paths.

Paths with common endpoints are internally vertex-disjoint when they share no other vertex.

For vertex sets $A,B$, the maximum number of pairwise vertex-disjoint $A$-$B$ paths equals the minimum size of a vertex set meeting every $A$-$B$ path.

In a $k$-connected graph, for a vertex $x$ and a set $Y$ of at least $k$ other vertices, there are $k$ paths from $x$ to distinct vertices of $Y$ that meet only at $x$. This follows from the Set version of Menger theorem by separating $x$ from $Y$.

A graph is $k$-linked when any $2k$ distinct vertices paired as $(x_i,y_i)$ can be joined by $k$ mutually vertex-disjoint paths from $x_i$ to $y_i$.

Unlike vertex connectivity, linkage specifies all endpoint pairings simultaneously.

On vertices $0,\dots ,7$, join cyclic indices differing by one or two modulo eight. The resulting planar graph has a square face bounded in order by $0,2,4,6$. Deleting at most three vertices cannot disconnect it: each break in the surviving cyclic chain requires two consecutive deleted vertices, and two separate breaks require four deletions. It is therefore four-connected. Disjoint paths joining $0$ to $4$ and $2$ to $6$ would cross in the complementary disk of the square face, contrary to the Jordan curve theorem. Thus four-connectivity does not guarantee two-linkage.

If a graph is $2k$-connected and has a graph minor $H$ satisfying $2\delta (H)\ge |H|+4k-1$, it is $k$-linked. Write $d=|H|-1-\delta (H)$, so $|H|\ge 2d+4k+1$. The rooted branch-set reduction replaces the minor model by $|H|-k$ disjoint connected sets, the first $2k$ containing any prescribed terminals separately, each missing at most $d$ of the remaining sets. Every prescribed pair then has at least $k+1$ common adjacent unused sets, allowing the $k$ connections to be selected successively. The reduction uses rooted separations of a graph, contraction of edges outside distinct branch sets, and a final Hall marriage theorem matching; the separation condition prevents a contraction from destroying access to the model.

Vertex connectivity $\kappa (G)$ is the smallest number of vertices whose deletion disconnects a nontrivial graph or reduces it to one vertex.

For a specified set $S$ of vertices, a rooted separation is a pair $(A,B)$ with $A\cup B=V(G)$, $S\subseteq A$, and no edges between $A\setminus B$ and $B\setminus A$. Its order is $|A\cap B|$. It avoids a branch set $C$ when $A\cap C=\varnothing$. A graph with vertex connectivity at least $|S|$ has no rooted separation of order below $|S|$ avoiding a nonempty branch set: both sides of such a separation would be nonempty after deleting its separator.

A graph with more than $k$ vertices is $k$-connected when deleting fewer than $k$ vertices always leaves it connected, equivalently when its vertex connectivity is at least $k$.

A $k$-connected graph has a cycle of length at least $\min \{|G|,2k\}$.

A component outside a longest cycle has at least $k$ attachment vertices in a $k$-connected graph, and no two attachments are consecutive, forcing cycle length at least $2k$.

A graph is 3-connected when it has at least four vertices and remains connected after deletion of any two vertices.

Edge connectivity $\lambda (G)$ is the smallest number of edges whose deletion disconnects the graph.

For every nontrivial graph, $\kappa (G)\le \lambda (G)\le \delta (G)$.

These compare two numerical invariants of connectivity with the minimum degree of a graph.

Two large cliques joined by a bipartite cross graph with edge count $\ell$ and vertex-cover number $k$ realize edge connectivity $\ell$ and vertex connectivity $k$ while preserving a chosen minimum degree.