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.

A linked graph is $k$-linked if it has at least $2k$ vertices and, for every choice of distinct terminals $s_1,\dots ,s_k,t_1,\dots ,t_k$, it has pairwise vertex-disjoint graph paths joining $s_i$ to $t_i$ for all $i$. The pairing is prescribed, which is stronger than the unpaired conclusion of the Menger theorem.

We prove the rooted dense minor linkage step carefully. We first prove the rooted branch-set reduction. Let $q\ge 2$ be even, let $S=\{x_1,\dots ,x_q\}$, and suppose a graph has $h$ disjoint nonempty vertex sets $C_1,\dots ,C_h$, where $h\ge d+3q/2$. Suppose each $G[C_i]$ is connected or every one of its graph components meets $S$, and each $C_i$ is adjacent to all but at most $d$ of the other $C_j$ not meeting $S$. Assume also that no rooted separation of a graph of order below $q$ avoids $d+1$ of these sets. Then there are $m=h-q/2$ disjoint connected vertex sets $D_1,\dots ,D_m$ such that $x_i\in D_i$ for $1\le i\le q$ and each of these first $q$ sets is adjacent to all but at most $d$ of $D_{q+1},\dots ,D_m$.

Here adjacency of sets means existence of an edge between them. A rooted separation of a graph is $(A,B)$ with $A\cup B=V(G)$, $S\subseteq A$, no edges between $A\setminus B$ and $B\setminus A$, and order $|A\cap B|$. It avoids $C_i$ when $A\cap C_i=\varnothing$. We prove the reduction by induction, first on the vertex count and then on the edge count; any counterexample chosen minimal in this ordering will be impossible.

We may delete edges joining two vertices of $S$. They cannot affect rooted separations of a graph, since $S$ lies wholly on the first side. Within a branch set, their deletion can only split a graph component into graph components each containing an endpoint in $S$, so the branch-set hypothesis also persists. An isolated vertex outside $S$ and all branch sets can be deleted. An isolated vertex $v\in S$ is also impossible, since $(S,V(G)\setminus \{v\})$ has order $q-1$ and avoids at least $h-q\ge d+q/2\ge d+1$ sets. Thus in a minimal counterexample $S$ is independent, and every isolated vertex outside $S$ belongs to a singleton branch set.

Consider a rooted separation of a graph $(A,B)$ of order exactly $q$ avoiding at least $d+1$ branch sets, and put $S^{\prime }=A\cap B$. Restrict to $G^{\prime }=G[B]-E(G[S^{\prime }])$ and $C_i^{\prime }=C_i\cap B$. Each $C_i^{\prime }$ is nonempty: any $C_i$ not itself avoided is adjacent to at least one of the $d+1$ avoided sets, and the endpoint of such an edge in $C_i$ must lie in $B$. If a graph component of $G^{\prime }[C_i^{\prime }]$ misses $S^{\prime }$, it lies in $B\setminus A$ and is a whole graph component of $G[C_i]$, with no vertex of $S$. The original hypothesis then forces $G[C_i]$ to be connected and $C_i^{\prime }=C_i$, entirely outside $A$. Thus each restricted set is connected or all its graph components meet $S^{\prime }$. In particular every $C_j^{\prime }$ missing $S^{\prime }$ equals an original set outside $A$, so all its required adjacencies from $C_i^{\prime }$ persist.

A rooted separation of a graph $(A^{\prime },B^{\prime })$ of $G^{\prime }$ avoiding $d+1$ restricted sets lifts to $(A\cup A^{\prime },B^{\prime })$ in $G$, of the same order: an avoided restricted set misses $S^{\prime }$, hence is an original set outside $A$. The edges removed inside $S^{\prime }$ do not obstruct lifting, since $S^{\prime }\subseteq A^{\prime }$. This proves the required separation hypothesis for $G^{\prime }$. If $G^{\prime }$ is smaller, induction gives the desired connected sets rooted at $S^{\prime }$. Moreover $G[A]$ has $q$ disjoint graph paths from $S$ to $S^{\prime }$, by the Menger theorem. Indeed a separator of smaller order between these sets would give a rooted separation of a graph of $G$ of smaller order still avoiding those $d+1$ original sets. Truncate the graph paths at their first visits to $S^{\prime }$, label their endpoints accordingly, and adjoin each graph path to the corresponding rooted connected set. They meet $B$ only in their distinct endpoints, so this gives the desired sets for $G$, a contradiction. Consequently in a minimal counterexample every such separation of order $q$ has $B=V(G)$ and $A=S$, an independent set.

Now contract any edge whose endpoints do not belong to two different branch sets. Its endpoints cannot both lie in $S$, so the image of $S$ still has size $q$. The branch-set conditions persist. If the contraction created a forbidden rooted separation of a graph of order below $q$, its lift would have order below $q$, except possibly when the contracted vertex lies in its separator. In that case the lifted order increases by one and is at most $q$. Equality would put the contracted edge inside $A$, contradicting the just-proved independence of $A$ for an order-$q$ separation avoiding $d+1$ sets. Thus the separation hypothesis also persists. Applying induction in the contracted graph and expanding the contracted vertex would produce the required disjoint connected sets. Hence every edge in a minimal counterexample joins two different branch sets.

Every vertex outside the branch sets would be isolated, since every edge joins two branch sets; such an isolated vertex could be deleted. Thus the branch sets cover the graph. Each nonsingleton branch set is therefore an independent set, and all its vertices belong to $S$, because each of its singleton graph components must meet $S$. Let $C$ be the union of the nonsingleton branch sets, and write $c=|C|\le q$. There is a matching in a graph from $C$ into $V(G)\setminus S$. Otherwise the Hall marriage theorem gives $X\subseteq C$ with neighbourhood $Y\subseteq V(G)\setminus S$ satisfying $|Y|<|X|$. Since $S$ is independent, $(S\cup Y,V(G)\setminus X)$ is a rooted separation of a graph of order $q-|X|+|Y|<q$. It avoids every singleton branch set outside $S\cup Y$, of which there are at leastThe penultimate counting bound uses that the nonsingleton sets number at most $c/2$, so $|V(G)|-c\ge h-c/2$. This contradicts the separation hypothesis.

Use that matching in a graph to make a two-vertex connected set for each terminal in $C$; terminals outside $C$ remain singleton sets. There are at leastunused vertices, all singleton original branch sets. Choose $m-q$ of them for the remaining $D_i$. Every rooted $D_i$ contains a singleton original branch set: either its terminal, or its terminal's matched neighbour. That singleton misses at most $d$ of the selected nonterminal singleton sets. This constructs exactly the desired family, contradicting minimality and proving the branch-set reduction.

Return to the given $22k$-connected graph. By the allowed assumption it has a graph minor $H$ with $2\delta (H)\ge h+4k-1$, where $h=|H|$. Put $d=h-1-\delta (H)$. ThenTake a branch-set model of $H$ and the $2k$ prescribed terminals as $S$. The branch sets are connected and each misses at most $d$ of the others. The separation hypothesis holds with $q=2k$: a separation of order below $2k$ avoiding a branch set would separate a surviving terminal from that set, contrary even to $2k$-connectivity. Since $h\ge d+3k$, the reduction applies. It produces $m=h-k$ sets with $s_i\in D_i$, $t_i\in D_{k+i}$, each terminal set missing at most $d$ of the $m-2k$ nonterminal sets. For each pair $D_i,D_{k+i}$ at leastnonterminal sets are adjacent to both. Choose different such sets for the $k$ pairs successively. The connected graph property inside the three sets and the two joining edges give a graph path from $s_i$ to $t_i$; take a simple graph path within their union. Different graph paths use disjoint sets. We have provedIn fact the argument proves the stronger transfer statement with $2k$-connectivity and the stated dense graph minor.

For the negative assertion, it suffices to give a value of $k$ for which the proposed general implication fails. Take $k=2$ and the graph on cyclic indices $0,\dots ,7$ in which two indices are adjacent when their cyclic distance is one or two. This is the four-connected planar obstruction to two-linkage. Draw the even cycle in a graph $0,2,4,6$ as the outer square, the odd cycle in a graph $1,3,5,7$ as an inner square rotated by $45$ degrees of vertices, and join each odd vertex to the two neighbouring even vertices; the annulus is triangulated without crossings. The outer face has vertices $0,2,4,6$ in this order.

Deleting at most three vertices leaves the graph connected. In cyclic order, consecutive surviving vertices are joined unless separated by a run of at least two deleted vertices. Disconnection requires two distinct such runs, hence at least four deletions. Conversely deleting the four neighbours of a vertex isolates it, so the vertex connectivity is exactly four. Disjoint graph paths joining $0$ to $4$ and $2$ to $6$ cannot exist: both would lie in the closed disk complementary to the outer face, and their endpoints alternate on its boundary. A first such graph path is a crosscut of the disk; the Jordan curve theorem puts the other two endpoints on opposite sides, forcing the second graph path to meet it. ThusThis is a counterexample to the unrestricted implication; no claim that the same construction works for every $k$ is needed.

A Plünnecke graph is a finite directed layered graph $V_0,\dots ,V_n$, with edges only from $V_i$ to $V_{i+1}$, satisfying two commutation conditions. For each edge $u\to v$, the successors of $v$ can be matched injectively into the successors of $u$, so that the matched predecessor has an edge to the original successor. Dually, the predecessors of $u$ can be matched injectively into the predecessors of $v$, so that each original predecessor has an edge to its match. These are upward and downward commutation. For nonempty bottom subsets define the graph magnification ratioAddition graphs have layer $A+iB$ and edges $x\to x+b$: exchanging the order of two additions gives exactly these matchings.

We prove a slightly stronger weighted cut lemma for commutative graphs, which also explains part (ii). Give vertices in $V_i$ weight $C^{-i}$, for any $C>0$. A separating set meets every bottom-to-top path. There is a minimum-weight separating set contained in $V_0\cup V_n$. We first establish its local three-layer step.

Consider a three-layer channel $U_0,U_1,U_2$, every vertex of which lies on a full path, and suppose the middle layer is a minimum-weight cut. Replacing a subset $Z\subseteq U_1$ by all its successors or all its predecessors still gives a cut. Minimality impliesLet $X_i\subseteq U_1$ be the vertices of incoming degree $i$. Partition $U_2$ into $T_i$ according to the largest incoming degree of one of their predecessors. ThenDownward commutation makes incoming degree nondecreasing along an edge. Thus every vertex of $T_i$ has at least $i$ predecessors, and summing the last inequalities over $j$ givesReverse all edges and interchange the endpoint layers. The graph still satisfies both commutation conditions, and the expansion factor becomes $C^{-1}$. The same argument now gives the opposite inequality $|E(U_0,U_1)|\ge C^{-1}|E(U_1,U_2)|$. Equality must therefore hold at every step. In particular the suffix inequality at $j=1$ is an equality, and the reversed argument givesConsequently the bottom layer has exactly the middle layer's weight. This proves the local replacement lemma.

For a general minimum cut $S$, write $S_i=S\cap V_i$, and take its highest nonempty intermediate portion $S_j$, $0<j<n$. Form the three-layer channel whose bottom vertices are reachable from $V_0$ while avoiding the earlier cut portions, and whose top vertices can reach $V_n\setminus S_n$. Its middle layer is exactly $S_j$: any other middle vertex would produce an uncut full path, while every member of $S_j$ is essential in a positive-weight minimum cut and hence lies on such a path when that vertex alone is allowed. Channels inherit the commutation matchings: the replacement intermediate vertices still join the same prefix and suffix paths.

The middle layer is a minimum cut within this channel, since a cheaper local separator would replace $S_j$ and make the global cut cheaper. Apply the local lemma, with weights scaled by the common factor $C^{-(j-1)}$, to replace $S_j$ by the channel's bottom layer. This does not increase weight and removes the highest intermediate cut layer. Repetition leaves a minimum cut in the endpoint layers, proving the weighted cut lemma. Vertices lying on no full path can first be deleted; when $D_n>0$ all bottom vertices survive, and deleting such branches can only decrease intermediate images, so proving the lower bounds in the channel suffices.

Now take $C=1$ and assume $D_n\ge 1$. If a minimum endpoint cut is $S_0\cup S_n$, then ${\mathrm{Im}}^{(n)}(V_0\setminus S_0)\subseteq S_n$, soThe bottom layer itself is a cut, so the minimum cut size is $|V_0|$. For every nonempty $Z\subseteq V_0$, the set $(V_0\setminus Z)\cup {\mathrm{Im}}^{(k)}Z$ is also a cut. Its size must be at least $|V_0|$, provingOne may also apply the permitted Menger theorem to obtain $|V_0|$ vertex-disjoint full paths, giving the same conclusion. The proof above establishes the needed cut statement directly.

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.

Let $q\ge 2$ be even, let $S=\{x_1,\dots ,x_q\}$, and suppose a graph has $h$ disjoint nonempty vertex sets $C_1,\dots ,C_h$, where $h\ge d+3q/2$. Suppose each $G[C_i]$ is connected or every one of its graph components meets $S$, and each $C_i$ is adjacent to all but at most $d$ of the other $C_j$ not meeting $S$. Assume also that no rooted separation of a graph of order below $q$ avoids $d+1$ of these sets. Then there are $m=h-q/2$ disjoint connected vertex sets $D_1,\dots ,D_m$ such that $x_i\in D_i$ for $1\le i\le q$ and each of these first $q$ sets is adjacent to all but at most $d$ of $D_{q+1},\dots ,D_m$.

Here adjacency of sets means existence of an edge between them. A rooted separation of a graph is $(A,B)$ with $A\cup B=V(G)$, $S\subseteq A$, no edges between $A\setminus B$ and $B\setminus A$, and order $|A\cap B|$. It avoids $C_i$ when $A\cap C_i=\varnothing$. We prove the reduction by induction, first on the vertex count and then on the edge count; any counterexample chosen minimal in this ordering will be impossible.

We may delete edges joining two vertices of $S$. They cannot affect rooted separations of a graph, since $S$ lies wholly on the first side. Within a branch set, their deletion can only split a graph component into graph components each containing an endpoint in $S$, so the branch-set hypothesis also persists. An isolated vertex outside $S$ and all branch sets can be deleted. An isolated vertex $v\in S$ is also impossible, since $(S,V(G)\setminus \{v\})$ has order $q-1$ and avoids at least $h-q\ge d+q/2\ge d+1$ sets. Thus in a minimal counterexample $S$ is independent, and every isolated vertex outside $S$ belongs to a singleton branch set.

Consider a rooted separation of a graph $(A,B)$ of order exactly $q$ avoiding at least $d+1$ branch sets, and put $S^{\prime }=A\cap B$. Restrict to $G^{\prime }=G[B]-E(G[S^{\prime }])$ and $C_i^{\prime }=C_i\cap B$. Each $C_i^{\prime }$ is nonempty: any $C_i$ not itself avoided is adjacent to at least one of the $d+1$ avoided sets, and the endpoint of such an edge in $C_i$ must lie in $B$. If a graph component of $G^{\prime }[C_i^{\prime }]$ misses $S^{\prime }$, it lies in $B\setminus A$ and is a whole graph component of $G[C_i]$, with no vertex of $S$. The original hypothesis then forces $G[C_i]$ to be connected and $C_i^{\prime }=C_i$, entirely outside $A$. Thus each restricted set is connected or all its graph components meet $S^{\prime }$. In particular every $C_j^{\prime }$ missing $S^{\prime }$ equals an original set outside $A$, so all its required adjacencies from $C_i^{\prime }$ persist.

A rooted separation of a graph $(A^{\prime },B^{\prime })$ of $G^{\prime }$ avoiding $d+1$ restricted sets lifts to $(A\cup A^{\prime },B^{\prime })$ in $G$, of the same order: an avoided restricted set misses $S^{\prime }$, hence is an original set outside $A$. The edges removed inside $S^{\prime }$ do not obstruct lifting, since $S^{\prime }\subseteq A^{\prime }$. This proves the required separation hypothesis for $G^{\prime }$. If $G^{\prime }$ is smaller, induction gives the desired connected sets rooted at $S^{\prime }$. Moreover $G[A]$ has $q$ disjoint graph paths from $S$ to $S^{\prime }$, by the Menger theorem. Indeed a separator of smaller order between these sets would give a rooted separation of a graph of $G$ of smaller order still avoiding those $d+1$ original sets. Truncate the graph paths at their first visits to $S^{\prime }$, label their endpoints accordingly, and adjoin each graph path to the corresponding rooted connected set. They meet $B$ only in their distinct endpoints, so this gives the desired sets for $G$, a contradiction. Consequently in a minimal counterexample every such separation of order $q$ has $B=V(G)$ and $A=S$, an independent set.

Now contract any edge whose endpoints do not belong to two different branch sets. Its endpoints cannot both lie in $S$, so the image of $S$ still has size $q$. The branch-set conditions persist. If the contraction created a forbidden rooted separation of a graph of order below $q$, its lift would have order below $q$, except possibly when the contracted vertex lies in its separator. In that case the lifted order increases by one and is at most $q$. Equality would put the contracted edge inside $A$, contradicting the just-proved independence of $A$ for an order-$q$ separation avoiding $d+1$ sets. Thus the separation hypothesis also persists. Applying induction in the contracted graph and expanding the contracted vertex would produce the required disjoint connected sets. Hence every edge in a minimal counterexample joins two different branch sets.

Every vertex outside the branch sets would be isolated, since every edge joins two branch sets; such an isolated vertex could be deleted. Thus the branch sets cover the graph. Each nonsingleton branch set is therefore an independent set, and all its vertices belong to $S$, because each of its singleton graph components must meet $S$. Let $C$ be the union of the nonsingleton branch sets, and write $c=|C|\le q$. There is a matching in a graph from $C$ into $V(G)\setminus S$. Otherwise the Hall marriage theorem gives $X\subseteq C$ with neighbourhood $Y\subseteq V(G)\setminus S$ satisfying $|Y|<|X|$. Since $S$ is independent, $(S\cup Y,V(G)\setminus X)$ is a rooted separation of a graph of order $q-|X|+|Y|<q$. It avoids every singleton branch set outside $S\cup Y$, of which there are at leastThe penultimate counting bound uses that the nonsingleton sets number at most $c/2$, so $|V(G)|-c\ge h-c/2$. This contradicts the separation hypothesis.

Use that matching in a graph to make a two-vertex connected set for each terminal in $C$; terminals outside $C$ remain singleton sets. There are at leastunused vertices, all singleton original branch sets. Choose $m-q$ of them for the remaining $D_i$. Every rooted $D_i$ contains a singleton original branch set: either its terminal, or its terminal's matched neighbour. That singleton misses at most $d$ of the selected nonterminal singleton sets. This constructs the desired family and completes the proof.