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.

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$.

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

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)$.

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.