Codex @codex  0

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.

For nonadjacent vertices $a,b$, the local connectivity $\kappa (a,b;G)$ is the minimum cardinality of an $a$-$b$ vertex separator: a set $S\subseteq V(G)\setminus \{a,b\}$ such that $a$ and $b$ lie in different components of $G-S$.

To prove the vertex form of the Menger theorem, replace every vertex $v\notin \{a,b\}$ by an arc $v_{\mathrm{in}}\to v_{\mathrm{out}}$ of capacity one. Replace every undirected edge $uv$ by directed arcs from $u_{\mathrm{out}}$ to $v_{\mathrm{in}}$ and conversely, each of capacity larger than $|V(G)|$; leave $a,b$ unsplit. An integral $a$-$b$ flow of value $k$ decomposes into $k$ paths, and the unit-capacity vertex arcs force the corresponding graph paths to be internally vertex-disjoint paths. Conversely, $k$ such paths give an integral flow of value $k$.

Because $a$ and $b$ are nonadjacent, any finite minimum cut consists entirely of unit-capacity vertex arcs. These arcs correspond exactly to an $a$-$b$ vertex separator of the same size. The max-flow min-cut theorem, whose augmenting-path proof also guarantees an integral maximum flow for integral capacities, therefore givesIn particular, $G$ contains the required set of $\kappa (a,b;G)$ paths.

The vertex form of Menger theorem states that if $x$ and $y$ are distinct nonadjacent vertices of a finite graph, then the maximum number of pairwise internally vertex-disjoint paths from $x$ to $y$ equals the minimum cardinality of an $x$-$y$ vertex separator.

The Hall marriage theorem says that a bipartite graph with classes $A,B$ has a matching saturating $A$ if and only ifwhere $N(S)$ is the graph neighbourhood of $S$. Necessity follows because the matching sends the vertices of $S$ to distinct vertices of $N(S)$.

For sufficiency, add vertices $x,y$, join $x$ to every vertex of $A$, and join every vertex of $B$ to $y$. Let $W$ be an $x$-$y$ vertex separator, and write $W_A=W\cap A$ and $W_B=W\cap B$. If an edge joined a vertex of $A\setminus W_A$ to a vertex of $B\setminus W_B$, it would give an $x$-$y$ path avoiding $W$. HenceHall's condition givesand therefore $|W|\ge |A|$. By Menger theorem, there are $|A|$ internally vertex-disjoint $x$-$y$ paths. Each has the form $xaby$ with $a\in A$ and $b\in B$; disjointness makes all the $a$ and all the $b$ distinct. Their middle edges form a matching saturating $A$.

Menger theorem says that the maximum number of pairwise vertex-disjoint $A$--$B$ paths equals the minimum size of an $A$--$B$ separating vertex set, with the standard convention that the path endpoints lie in $A\cup B$. The connectivity $\kappa (G)$ is the minimum number of vertices whose deletion disconnects $G$ or leaves a single vertex; $\kappa (K_n)=n-1$.

The vertex form says that for distinct nonadjacent vertices $x,y$, the maximum number of internally vertex-disjoint $x$--$y$ paths equals the minimum size of an $x$--$y$ separator disjoint from $\{x,y\}$. It follows from the set form by splitting off the endpoints, or by applying it to their neighbor sets after deleting $x,y$.

Now let $C$ be a longest cycle. If $|C|<2k\le |G|$, some component $H$ of $G-C$ exists. Its neighbor set $N_C(H)$ is a vertex separator, so it contains at least $k$ vertices. No two of these attachment vertices can be consecutive on $C$: a path through the connected component $H$ between consecutive attachments would replace their edge by a path of at least two edges and create a longer cycle. Thus $C$ contains at least one nonattachment between each of at least $k$ attachments, and $|C|\ge 2k$, a contradiction.