[proofplan] Write $\kappa_{a,b}(G)$ for the minimum size of an $a$–$b$ separator. The inequality "maximum number of internally disjoint paths $\leq \kappa_{a,b}(G)$" is immediate: every separator hits each disjoint path at a distinct internal vertex. The substance is the reverse inequality, which we prove by contradiction using a minimal counterexample $(G, a, b)$ — first $k := \kappa_{a,b}(G)$ minimal, then $|E(G)|$ minimal. We fix a minimum separator $S$ and distinguish two cases. If $S$ is neither $N(a)$ nor $N(b)$, the two sides of $S$ in $G - S$ yield two strictly smaller graphs $G_a, G_b$ (obtained by collapsing the other side to a single vertex), to which minimality applies; the disjoint paths in $G_a$ and $G_b$ glue along $S$ into $k$ internally disjoint $a$–$b$ paths in $G$. If $S = N(a)$ (or symmetrically $N(b)$), we use a shortest $a$–$b$ path and a carefully chosen edge deletion to produce a new size-$k$ separator that is neither $N(a)$ nor $N(b)$, reducing to the first case. [/proofplan] [step:Prove the easy inequality: the maximum number of internally disjoint paths is at most $\kappa_{a,b}(G)$] Let $P_1, \ldots, P_m$ be internally disjoint $a$–$b$ paths in $G$. Since $a \not\sim b$, every $a$–$b$ path has length at least $2$ and hence contains at least one internal vertex. Fix an internal vertex $v_i$ of $P_i$ for each $i$; internal-disjointness gives $v_i \neq v_j$ for $i \neq j$. Let $T \subseteq V(G) \setminus \{a, b\}$ be any $a$–$b$ separator. For each $i$, the path $P_i$ must meet $T$: otherwise $P_i$ survives in $G - T$, providing an $a$–$b$ path in $G - T$. Choose $w_i \in V(P_i) \cap T$ (necessarily internal, since $a, b \notin T$). Internal-disjointness of the $P_i$ forces $w_i \neq w_j$ for $i \neq j$, so \begin{align*} |T| \geq m. \end{align*} Specializing to a minimum separator gives $\kappa_{a,b}(G) \geq m$. Taking the supremum over all disjoint-path families yields the easy inequality. [/step] [step:Set up the minimal counterexample and dispose of the small-$k$ cases] Suppose the reverse inequality fails somewhere. Among all pairs $(H, u, v)$ with $H$ connected, $u \neq v \in V(H)$, $u \not\sim v$, and the maximum number of internally disjoint $u$–$v$ paths strictly less than $\kappa_{u,v}(H)$, choose one minimizing $\kappa_{u,v}(H)$; among those, choose one minimizing $|E(H)|$. Call this minimal counterexample $(G, a, b)$ and set $k := \kappa_{a,b}(G)$. **$k \geq 2$.** If $k = 0$, then $\varnothing$ separates $a$ from $b$, contradicting connectedness of $G$. If $k = 1$, let $\{s\}$ be a single-vertex separator. Since $G$ is connected, some $a$–$b$ path exists, and every such path must pass through $s$; thus there is at least one internally disjoint $a$–$b$ path, matching $k = 1$ and contradicting the counterexample property. Fix a minimum $a$–$b$ separator $S \subseteq V(G)$, so $|S| = k \geq 2$. Let $A$ be the set of vertices reachable from $a$ in $G - S$, and $B$ the set reachable from $b$ in $G - S$. Since $S$ separates $a$ from $b$, $A \cap B = \varnothing$; by definition $a \in A$, $b \in B$, and $A \cup B \cup S$ covers every vertex that lies in some $a$- or $b$-component of $G - S$ (other vertices, if any, belong to further components of $G - S$). **Every $s \in S$ has a neighbour in $A$ and a neighbour in $B$.** If some $s \in S$ had no neighbour in $A$, then $S \setminus \{s\}$ would still separate $a$ from $b$: any $a$–$b$ path in $G - (S \setminus \{s\})$ would pass through $s$, so its vertex immediately preceding $s$ is a neighbour of $s$ reachable from $a$ in $G - S$, which lies in $A$ — contradiction. By symmetry, $s$ has a neighbour in $B$ as well. [/step] [step:Handle the case $S \neq N(a)$ and $S \neq N(b)$ by splitting $G$ along $S$ and recombining] **Case 1: $S \neq N(a)$ and $S \neq N(b)$.** Pick vertices $v_a \in N(a) \setminus S$ and $v_b \in N(b) \setminus S$; these exist by the case assumption. Since $v_a \notin S$ and $v_a \sim a$, the vertex $v_a$ is reachable from $a$ in $G - S$, so $v_a \in A$; symmetrically $v_b \in B$. In particular $|A| \geq 2$ and $|B| \geq 2$. **Construction of the auxiliary graphs.** Introduce two new vertices $c_a, c_b \notin V(G)$ and define \begin{align*} G_a &: V(G_a) = (A \cup S) \cup \{c_a\}, & E(G_a) &= E(G[A \cup S]) \cup \{\{s, c_a\} : s \in S\}, \\ G_b &: V(G_b) = (B \cup S) \cup \{c_b\}, & E(G_b) &= E(G[B \cup S]) \cup \{\{s, c_b\} : s \in S\}. \end{align*} In $G_a$ the vertex $c_a$ is adjacent exactly to $S$; since $a \notin S$, we have $a \not\sim c_a$. Symmetrically $c_b \not\sim b$ in $G_b$. **Connectedness.** $G_a$ is connected: $G[A]$ is connected (as $A$ is a union of connected components of $G - S$ reachable from $a$, hence connected), and every $s \in S$ is adjacent to some vertex of $A$ (shown above) and to $c_a$. Likewise $G_b$ is connected. [claim:The auxiliary graphs have strictly fewer edges, $|E(G_a)| < |E(G)|$ and $|E(G_b)| < |E(G)|$] [proof] No edge of $G$ joins $A$ to $B$, because $A$ and $B$ lie in distinct components of $G - S$. Partitioning $E(G)$ according to whether each edge lies entirely in $A \cup S$, entirely in $B \cup S$, or has an endpoint outside $A \cup B \cup S$, and using that every vertex lies in $A \cup B \cup S$ (if not, it is in some further component of $G - S$, which we may absorb into either $A$ or $B$ — for the counting, redefine $B$ if necessary to be the union of all components of $G - S$ other than the one containing $a$; this preserves $a \in A$, $b \in B$, $A \cap B = \varnothing$, and every $s \in S$ still has a neighbour in $A$ and in $B$ by the same argument), we obtain \begin{align*} |E(G)| = |E(G[A \cup S])| + |E(G[B \cup S])| - |E(G[S])|, \end{align*} since edges within $S$ are counted once in each of the two induced subgraphs. On the other hand $|E(G_a)| = |E(G[A \cup S])| + k$, hence \begin{align*} |E(G)| - |E(G_a)| = |E(G[B \cup S])| - |E(G[S])| - k. \end{align*} The quantity $|E(G[B \cup S])| - |E(G[S])|$ counts the edges of $G$ with at least one endpoint in $B$, i.e., edges within $B$ together with edges from $B$ to $S$. Each $s \in S$ has at least one neighbour in $B$, contributing at least $k$ edges from $B$ to $S$ (one per $s \in S$, all distinct). Additionally, $v_b \in B$ is adjacent to $b \in B$, so $\{v_b, b\}$ is an edge of $G[B]$ (an edge within $B$), which is not among the $B$-to-$S$ edges. Therefore \begin{align*} |E(G[B \cup S])| - |E(G[S])| \geq k + 1, \end{align*} and $|E(G)| - |E(G_a)| \geq 1$, proving $|E(G_a)| < |E(G)|$. The inequality $|E(G_b)| < |E(G)|$ follows by the symmetric argument using $v_a \in A$ and the edge $\{a, v_a\}$. [/proof] [/claim] [claim:$\kappa_{a, c_a}(G_a) \geq k$ and $\kappa_{c_b, b}(G_b) \geq k$] [proof] Let $T \subseteq V(G_a) \setminus \{a, c_a\}$ separate $a$ from $c_a$ in $G_a$; then $T \subseteq A \cup S$. We show $T$ is also an $a$–$b$ separator in $G$. Suppose for contradiction that $P$ is an $a$–$b$ path in $G - T$. Since $S$ separates $a$ from $b$ in $G$, $P$ meets $S$; let $s^*$ be the first vertex of $S$ on $P$. The sub-walk of $P$ from $a$ to $s^*$ stays in $A \cup S$ (every vertex before $s^*$ is outside $S$ and reachable from $a$ without passing through $S$, hence in $A$); call this sub-walk $P'$. Then $P'$ is an $a$–$s^*$ path in $G[A \cup S] - T$. Appending the edge $\{s^*, c_a\} \in E(G_a)$ yields an $a$–$c_a$ path in $G_a - T$, contradicting that $T$ separates $a$ from $c_a$ in $G_a$. Hence every $a$–$c_a$ separator in $G_a$ is an $a$–$b$ separator in $G$, forcing $\kappa_{a, c_a}(G_a) \geq \kappa_{a,b}(G) = k$. The inequality for $G_b$ is symmetric. [/proof] [/claim] **Applying minimality.** The pair $(G_a, a, c_a)$ has $a \not\sim c_a$ (established above), is connected, has $\kappa_{a, c_a}(G_a) \geq k$, and satisfies $|E(G_a)| < |E(G)|$. If $\kappa_{a, c_a}(G_a) > k$, then $(G_a, a, c_a)$ is not a minimal-$\kappa$ counterexample because $k$ was chosen minimal; moreover it also has fewer edges, so it is not a counterexample at all, meaning there exist $\kappa_{a, c_a}(G_a) \geq k$ internally disjoint $a$–$c_a$ paths in $G_a$. If $\kappa_{a, c_a}(G_a) = k$, then $(G_a, a, c_a)$ is not a counterexample by the edge-minimality of $G$ at connectivity $k$, again yielding at least $k$ internally disjoint $a$–$c_a$ paths. In either case, fix a family $P_1^a, \ldots, P_k^a$ of internally disjoint $a$–$c_a$ paths in $G_a$. Symmetrically, fix a family $P_1^b, \ldots, P_k^b$ of internally disjoint $c_b$–$b$ paths in $G_b$. **Matching entry vertices.** Each $P_i^a$ reaches $c_a$ via some neighbour of $c_a$, i.e., some $s_i^a \in S$; and the $s_i^a$ are distinct across $i$, since paths sharing an $S$-vertex would share an internal vertex, violating internal-disjointness. As there are $k$ distinct values $s_i^a \in S$ and $|S| = k$, the map $i \mapsto s_i^a$ is a bijection from $[k]$ to $S$. Relabel the paths so that $s_i^a = s_i$ for a fixed enumeration $S = \{s_1, \ldots, s_k\}$. Analogously, relabel the $P_j^b$ so that $P_i^b$ reaches $c_b$ through $s_i$. **Stitching.** For each $i \in [k]$, define $Q_i$ as the concatenation of the prefix of $P_i^a$ from $a$ to $s_i$ (deleting the final edge $\{s_i, c_a\}$) with the suffix of $P_i^b$ from $s_i$ to $b$ (deleting the initial edge $\{c_b, s_i\}$). The prefix is a path in $G[A \cup S]$ from $a$ to $s_i$; the suffix is a path in $G[B \cup S]$ from $s_i$ to $b$. Both are paths in $G$, and they share only the vertex $s_i$: the prefix's vertices lie in $A \cup S$, the suffix's lie in $B \cup S$, and $A \cap B = \varnothing$, so any common vertex is in $S$. But the prefix meets $S$ only at its final vertex $s_i$ (any earlier $S$-vertex would, together with the $\{s, c_a\}$-edge, cut short the path $P_i^a$, forcing the path to have already reached $c_a$), and the suffix meets $S$ only at its initial vertex $s_i$ (analogously). Hence $Q_i$ is an $a$–$b$ path in $G$. **Internal disjointness of $Q_1, \ldots, Q_k$.** For $i \neq j$, we check that $Q_i$ and $Q_j$ share no internal vertex: - Within $A$: the prefix-internal vertices of $Q_i$ and $Q_j$ lie in $V(P_i^a) \cap A$ and $V(P_j^a) \cap A$, which are disjoint by internal-disjointness of $P_i^a, P_j^a$ (and $a$ is an endpoint, not internal). - Within $B$: symmetric. - In $S$: the only $S$-vertex internal to $Q_i$ is $s_i$, and $s_i \neq s_j$. - Across $A$ and $B$: impossible since $A \cap B = \varnothing$. Thus $Q_1, \ldots, Q_k$ are $k$ internally disjoint $a$–$b$ paths in $G$, contradicting that $(G, a, b)$ is a counterexample. Hence Case 1 cannot occur. [guided] The guiding principle of Case 1 is "split and recombine": cut $G$ along the separator $S$ into two halves, apply the inductive hypothesis (via minimality) to each half separately, then stitch the resulting path systems back together at $S$. The auxiliary vertices $c_a$ and $c_b$ package the "other side" of each half into a single target, converting "paths from $a$ across to $S$" in the $A$-side into honest "$a$–$c_a$ paths" — the shape of data Menger's theorem consumes. **Setting up the halves.** The case hypothesis gives us vertices $v_a \in N(a) \setminus S$ and $v_b \in N(b) \setminus S$. Since $v_a$ is adjacent to $a$ and avoids $S$, it stays in the $a$-component of $G - S$, so $v_a \in A$; symmetrically $v_b \in B$. This gives us "genuine" vertices inside each half beyond just $a$ and $b$, which is exactly what we will use to count edges. The graphs $G_a, G_b$ collapse the other half to a single vertex: $G_a = G[A \cup S]$ with a new vertex $c_a$ joined to all of $S$. Note $a \not\sim c_a$ because $c_a$'s only neighbours are in $S$ and $a \notin S$ — so the theorem's non-adjacency hypothesis is preserved. Both graphs are connected: each $s \in S$ has a neighbour in $A$ (a standard fact about minimum separators: if not, $S \setminus \{s\}$ would still separate), hence connects $S$ to $A$, and $c_a$ is adjacent to all of $S$. **The strict edge drop.** To invoke minimality on $(G_a, a, c_a)$ we need $|E(G_a)| < |E(G)|$. The clean way is to compare the two sides directly. Because $G - S$ has no edges across the partition $A / B$, \begin{align*} |E(G)| = |E(G[A \cup S])| + |E(G[B \cup S])| - |E(G[S])|, \end{align*} where we subtract $|E(G[S])|$ because edges inside $S$ are counted once in each induced subgraph. Since $G_a$ replaces the $B$-side $G[B \cup S]$ by a star $c_a$–$S$ of $k$ edges, \begin{align*} |E(G)| - |E(G_a)| = |E(G[B \cup S])| - |E(G[S])| - k. \end{align*} The right-hand side is the number of $G$-edges touching $B$ (edges within $B$ plus edges from $B$ to $S$), minus $k$. Each $s \in S$ has at least one neighbour in $B$, contributing $\geq k$ edges from $B$ to $S$. On top of that, the vertex $v_b \in B \setminus S$ (which exists because $S \neq N(b)$) has an edge $\{v_b, b\}$ which lies strictly within $B$, beyond those $k$ edges. So the right-hand side is $\geq 1$, giving the strict inequality $|E(G_a)| < |E(G)|$. The inequality $|E(G_b)| < |E(G)|$ is symmetric, using $v_a \in A$ and the edge $\{a, v_a\}$. **Separators transfer.** To apply minimality we also need $\kappa_{a, c_a}(G_a) \geq k$, so that $(G_a, a, c_a)$ actually falls under the induction at connectivity at least $k$. The key is that any $a$–$c_a$ separator $T$ in $G_a$ is also an $a$–$b$ separator in $G$: in $G_a$, every path from $a$ to $c_a$ must ultimately touch $S$ (since $c_a$'s neighbours are $S$), so removing $T$ disconnects $a$ from $S$ inside $A \cup S$. But every $a$–$b$ path in $G$ crosses $S$, so the same $T$ disconnects $a$ from $b$ in $G$. Hence $|T| \geq \kappa_{a,b}(G) = k$. **Invoking minimality.** Now $(G_a, a, c_a)$ has $\kappa \geq k$ and strictly fewer edges than $G$. Whether $\kappa(G_a, a, c_a)$ equals $k$ or exceeds it, minimality forbids $(G_a, a, c_a)$ from being a counterexample: if $\kappa > k$, it would violate "$k$ minimal among counterexample connectivities"; if $\kappa = k$, it would violate "$|E(G)|$ minimal among $\kappa = k$ counterexamples". So Menger's theorem holds for $(G_a, a, c_a)$, giving at least $k$ internally disjoint $a$–$c_a$ paths in $G_a$; fix exactly $k$ of them, $P_1^a, \ldots, P_k^a$. Symmetrically in $G_b$, fix $P_1^b, \ldots, P_k^b$ internally disjoint $c_b$–$b$ paths. **Why the paths hit $S$ bijectively.** Each $P_i^a$ ends at $c_a$ through one of $c_a$'s neighbours, i.e., through some $s_i^a \in S$. Internal-disjointness forces the $s_i^a$ to be distinct: two paths ending via the same $s \in S$ would share $s$ as an internal vertex. We have $k$ distinct entry points and $|S| = k$, so the entry map $i \mapsto s_i^a$ is a bijection onto $S$. Relabelling, assume $P_i^a$ enters $c_a$ through $s_i$ for a fixed enumeration $S = \{s_1, \ldots, s_k\}$. Matching up the $P_j^b$ the same way, we align the halves: both $P_i^a$ and $P_i^b$ use the "gate" $s_i$. **Stitching.** Define $Q_i$ by concatenating the $a$-to-$s_i$ prefix of $P_i^a$ (drop the final edge $\{s_i, c_a\}$) with the $s_i$-to-$b$ suffix of $P_i^b$ (drop the initial edge $\{c_b, s_i\}$). The prefix lives in $G[A \cup S]$ and the suffix in $G[B \cup S]$, and both are genuine paths in $G$. They share only $s_i$: a common vertex must lie in $(A \cup S) \cap (B \cup S) = S$ (since $A \cap B = \varnothing$), but the prefix meets $S$ only at its terminal vertex $s_i$ (if it hit $S$ earlier, the path $P_i^a$ could have ended at $c_a$ earlier, contradicting that it is a path and reaches $c_a$ only at the end), and likewise the suffix meets $S$ only at its initial vertex $s_i$. So $Q_i$ is a well-defined $a$–$b$ path in $G$. **Internal disjointness of the $Q_i$.** For $i \neq j$, we compare internal vertices: - In $A$: internal $A$-vertices of $Q_i$ and $Q_j$ come from the prefix halves, which are internally disjoint because the $P_i^a$ are. - In $B$: symmetric. - In $S$: $Q_i$'s only internal $S$-vertex is $s_i$ (the gluing point), and the $s_i$ are distinct. - Crossing $A$ and $B$: impossible, as $A \cap B = \varnothing$. Thus $Q_1, \ldots, Q_k$ are $k$ internally disjoint $a$–$b$ paths in $G$. This contradicts the assumption that $(G, a, b)$ is a counterexample, so Case 1 is impossible. [/guided] [/step] [step:Reduce the case $S = N(a)$ to Case 1 via a shortest path and an edge deletion] **Case 2: $S = N(a)$.** The subcase $S = N(b)$ is handled by swapping the roles of $a$ and $b$. We have $|N(a)| = |S| = k \geq 2$. [claim:$N(a) \cap N(b) = \varnothing$] [proof] Suppose $x \in N(a) \cap N(b)$. Consider $(G - x, a, b)$. We have $a \not\sim b$ in $G - x$ (since $a \not\sim b$ in $G$) and $G - x$ is connected if it is; if it is disconnected, every $a$–$b$ path in $G$ uses $x$, so $\{x\}$ separates $a$ from $b$ in $G$ and $k \leq 1$, contradicting $k \geq 2$. So $G - x$ is connected. If $T$ is an $a$–$b$ separator in $G - x$, then $T \cup \{x\}$ is an $a$–$b$ separator in $G$: any $a$–$b$ path in $G - (T \cup \{x\})$ avoids $x$ and hence is an $a$–$b$ path in $(G - x) - T$, contradicting $T$ being a separator in $G - x$. Therefore $\kappa_{a,b}(G - x) \geq \kappa_{a,b}(G) - 1 = k - 1$. Since $\kappa_{a,b}(G - x) \geq k - 1$, and the minimality of $k$ makes $(G - x, a, b)$ not a counterexample at $\kappa < k$ (and, as shown in the Case 1 analysis, not a counterexample at $\kappa \geq k$ either, if $|E(G - x)| < |E(G)|$ — which it is, since removing a vertex removes at least the edge $\{a, x\}$), there exist at least $k - 1$ internally disjoint $a$–$b$ paths in $G - x$. Adjoining the length-$2$ path $a, x, b$ (valid since $x \in N(a) \cap N(b)$) produces $k$ internally disjoint $a$–$b$ paths in $G$ (the new path's unique internal vertex is $x$, absent from $G - x$). This contradicts that $(G, a, b)$ is a counterexample. [/proof] [/claim] **Shortest $a$–$b$ path.** Since $G$ is connected and $a \neq b$, there is an $a$–$b$ path. Choose a shortest one, say $a = x_0, x_1, \ldots, x_\ell, x_{\ell+1} = b$ (so the path has length $\ell + 1$). By definition $x_1 \in N(a)$. If $\ell = 1$, then $x_1 = x_\ell \in N(b)$, contradicting $N(a) \cap N(b) = \varnothing$. Hence $\ell \geq 2$, so $x_2$ is well-defined, $x_2 \neq b$, and the edge $\{x_1, x_2\}$ is an internal edge of the path. **Edge deletion $G' := G - \{x_1, x_2\}$.** Here $G - \{x_1, x_2\}$ denotes edge-deletion (vertices unchanged). [claim:$\kappa_{a,b}(G') = k - 1$] [proof] *Upper bound.* Suppose $\kappa_{a,b}(G') \geq k$. Since $|E(G')| = |E(G)| - 1 < |E(G)|$, by the minimality argument (fewer edges at connectivity at least $k$, see the analogous step in Case 1), $(G', a, b)$ is not a counterexample: there exist $\kappa_{a,b}(G') \geq k$ internally disjoint $a$–$b$ paths in $G'$. Any such path in $G'$ is also an $a$–$b$ path in $G$ (edges of $G'$ are edges of $G$), giving $k$ internally disjoint $a$–$b$ paths in $G$, contradicting that $(G, a, b)$ is a counterexample. Therefore $\kappa_{a,b}(G') \leq k - 1$. *Lower bound.* Let $\tilde T$ be an $a$–$b$ separator in $G'$. We claim $\tilde T \cup \{x_1\}$ is an $a$–$b$ separator in $G$. Let $P$ be any $a$–$b$ path in $G - (\tilde T \cup \{x_1\})$. Then $P$ avoids $x_1$, so $P$ does not use the edge $\{x_1, x_2\}$; hence $P$ is a path in $G - \{x_1, x_2\} - \tilde T = G' - \tilde T$, contradicting that $\tilde T$ separates in $G'$. Therefore $\tilde T \cup \{x_1\}$ separates in $G$, so $|\tilde T| + 1 \geq \kappa_{a,b}(G) = k$, giving $|\tilde T| \geq k - 1$. Taking $\tilde T$ minimum yields $\kappa_{a,b}(G') \geq k - 1$. Combining, $\kappa_{a,b}(G') = k - 1$. [/proof] [/claim] Fix a minimum $a$–$b$ separator $\tilde S$ of $G'$ with $|\tilde S| = k - 1$. By the same argument as the lower bound above (applied with $\tilde T = \tilde S$), both $\tilde S \cup \{x_1\}$ and $\tilde S \cup \{x_2\}$ are size-$k$ $a$–$b$ separators in $G$. [claim:At least one of $\tilde S \cup \{x_1\}, \tilde S \cup \{x_2\}$ is neither $N(a)$ nor $N(b)$] [proof] We analyse $\tilde S \cup \{x_2\}$ first. *Not $N(a)$.* If $\tilde S \cup \{x_2\} = N(a)$, then $x_2 \in N(a)$, so $\{a, x_2\} \in E(G)$. Then $a, x_2, x_3, \ldots, x_{\ell+1} = b$ is an $a$–$b$ walk of length $\ell$, shorter than the shortest-path length $\ell + 1$ — contradiction. Therefore $\tilde S \cup \{x_2\} \neq N(a)$. *Is $\tilde S \cup \{x_2\} = N(b)$ possible?* This would require $x_2 \in N(b)$, i.e., $\{x_2, b\} \in E(G)$. Then $a, x_1, x_2, b$ is an $a$–$b$ walk of length $3$, forcing the shortest path to have length at most $3$, i.e., $\ell + 1 \leq 3$, i.e., $\ell \leq 2$. Since $\ell \geq 2$, this forces $\ell = 2$. In this subcase, we switch to analysing $\tilde S \cup \{x_1\}$. In the subcase $\ell = 2$ with $\tilde S \cup \{x_2\} = N(b)$, we have $\tilde S = N(b) \setminus \{x_2\}$. Consider $\tilde S \cup \{x_1\}$: - *Not $N(b)$.* If $\tilde S \cup \{x_1\} = N(b)$, then $x_1 \in N(b)$, contradicting $N(a) \cap N(b) = \varnothing$ since $x_1 \in N(a)$. - *Not $N(a)$.* If $\tilde S \cup \{x_1\} = N(a)$, then $\tilde S = N(a) \setminus \{x_1\}$. Combined with $\tilde S = N(b) \setminus \{x_2\}$, this gives $N(a) \setminus \{x_1\} = N(b) \setminus \{x_2\}$. This common set has size $k - 1 \geq 1$; pick any $y$ in it. Then $y \in N(a)$ and $y \in N(b)$, so $y \in N(a) \cap N(b) = \varnothing$ — contradiction. Hence in the subcase $\ell = 2$ with $\tilde S \cup \{x_2\} = N(b)$, the separator $\tilde S \cup \{x_1\}$ is neither $N(a)$ nor $N(b)$. In every other situation, $\tilde S \cup \{x_2\}$ itself is neither $N(a)$ (just shown) nor $N(b)$ (by exclusion of the special subcase). [/proof] [/claim] Denote by $S'$ the size-$k$ separator produced by the previous claim, so $S' \in \{\tilde S \cup \{x_1\}, \tilde S \cup \{x_2\}\}$ with $S' \neq N(a)$ and $S' \neq N(b)$. **Reduction to Case 1.** The triple $(G, a, b)$ with minimum separator $S'$ satisfies the hypotheses of Case 1 ($|S'| = k = \kappa_{a,b}(G)$, $S' \neq N(a)$, $S' \neq N(b)$). But Case 1 has been shown to be impossible for a counterexample. This contradicts the assumption that $(G, a, b)$ is a counterexample with $S = N(a)$. The subcase $S = N(b)$ is handled by symmetry. Hence Case 2 is also impossible. [guided] Case 2 handles the "degenerate" situation where the minimum separator sits tightly against $a$ (or by symmetry against $b$). The strategy: although $S = N(a)$ does not directly fit Case 1, we will find a *different* minimum separator $S'$ of the same size $k$ that is not a neighbourhood, and then Case 1's argument applies to $(G, a, b, S')$ to produce a contradiction. **Disjointness of $N(a)$ and $N(b)$.** If some $x$ were a common neighbour, we could delete it and apply minimality: in $G - x$, we still have $a \not\sim b$, and any separator in $G - x$ becomes a separator in $G$ by adjoining $x$ (because any $a$–$b$ path in $G$ avoiding $x$ is a path in $G - x$). So $\kappa_{a,b}(G - x) \geq k - 1$. With $G - x$ having strictly fewer edges than $G$ and $\kappa \geq k - 1$, minimality rules out $(G - x, a, b)$ as a counterexample at any allowable $\kappa$. Hence $G - x$ admits at least $k - 1$ internally disjoint $a$–$b$ paths, and adjoining the length-$2$ path $a, x, b$ (whose unique internal vertex $x$ was deleted from $G - x$, so it shares no internal vertex with the others) gives $k$ internally disjoint paths in $G$. No counterexample — so $N(a) \cap N(b) = \varnothing$. **Shortest path, with $\ell \geq 2$.** A shortest $a$–$b$ path $a = x_0, x_1, \ldots, x_\ell, b$ has length $\ell + 1 \geq 2$ (since $a \not\sim b$). If $\ell = 1$, then the path is $a, x_1, b$ with $x_1 \in N(a) \cap N(b)$, but that intersection is empty. So $\ell \geq 2$, giving an internal edge $\{x_1, x_2\}$ with $x_2 \neq b$ — the edge we will delete. **Deleting the edge reduces connectivity by exactly one.** Let $G' = G - \{x_1, x_2\}$ (just the edge). Two directions: - *Not up from $k$*: If $\kappa_{a,b}(G') \geq k$, then $G'$ has fewer edges and still $\kappa \geq k$, so by the minimality argument (same shape as in Case 1) $G'$ is not a counterexample; so it has $k$ disjoint $a$–$b$ paths, which are also paths in $G$ — contradicting that $G$ is a counterexample. - *Not down more than one*: A minimum separator $\tilde T$ in $G'$, augmented by $x_1$, still separates in $G$: any $a$–$b$ path in $G$ that avoids $x_1$ cannot use the edge $\{x_1, x_2\}$, hence it is a path in $G'$ and is blocked by $\tilde T$. So $|\tilde T| + 1 \geq k$, giving $\kappa_{a,b}(G') \geq k - 1$. Combining, $\kappa_{a,b}(G') = k - 1$. Fix a minimum separator $\tilde S$ of $G'$ with $|\tilde S| = k - 1$. The same "augment by $x_1$" argument, reapplied, shows $\tilde S \cup \{x_1\}$ is a separator in $G$ of size $k$; symmetrically $\tilde S \cup \{x_2\}$ is also a size-$k$ separator in $G$. These are our two candidate replacements for $S$. **One of the two is neither $N(a)$ nor $N(b)$.** We check candidates. *Start with $\tilde S \cup \{x_2\}$.* Is this $N(a)$? Only if $x_2 \in N(a)$, in which case $a, x_2, x_3, \ldots, b$ is an $a$–$b$ walk of length $\ell$ (shorter than the length-$(\ell+1)$ shortest path), which is a contradiction. So $\tilde S \cup \{x_2\} \neq N(a)$. Is it $N(b)$? Only if $x_2 \in N(b)$, hence the walk $a, x_1, x_2, b$ has length $3$, forcing $\ell + 1 \leq 3$, i.e., $\ell = 2$. In all situations except this very specific one, $\tilde S \cup \{x_2\}$ is itself neither $N(a)$ nor $N(b)$ and we are done. *The special subcase $\ell = 2$, $\tilde S \cup \{x_2\} = N(b)$.* Here we switch to $\tilde S \cup \{x_1\}$ and verify the same two conditions: - Not $N(b)$: if $\tilde S \cup \{x_1\} = N(b)$ then $x_1 \in N(b)$, but $x_1 \in N(a)$ and $N(a) \cap N(b) = \varnothing$ — contradiction. - Not $N(a)$: if $\tilde S \cup \{x_1\} = N(a)$ then $\tilde S = N(a) \setminus \{x_1\}$. Combined with $\tilde S = N(b) \setminus \{x_2\}$ (from the subcase hypothesis), we get $N(a) \setminus \{x_1\} = N(b) \setminus \{x_2\}$, a set of size $k - 1 \geq 1$ contained in both $N(a)$ and $N(b)$, contradicting $N(a) \cap N(b) = \varnothing$. So in this subcase $\tilde S \cup \{x_1\}$ is the valid replacement. In every situation we have a size-$k$ separator $S'$ of $G$ that is neither $N(a)$ nor $N(b)$. **Reducing to Case 1.** The triple $(G, a, b)$ with this new minimum separator $S'$ satisfies the hypotheses of Case 1, but Case 1 produced a contradiction for any minimal counterexample. So Case 2 also fails, and no minimal counterexample exists. [/guided] [/step] [step:Collect the two inequalities and conclude] Cases 1 and 2 together exhaust the possibilities for the minimum separator $S$ in the minimal counterexample (either $S$ equals one of $N(a), N(b)$, or it equals neither). Each case yields a contradiction, so no counterexample exists: for every connected $G$ and every pair of non-adjacent $a \neq b \in V(G)$, there exist $\kappa_{a,b}(G)$ internally disjoint $a$–$b$ paths. Combining with the easy inequality (maximum number of disjoint paths $\leq \kappa_{a,b}(G)$), we obtain \begin{align*} \max\{m : \text{there are } m \text{ internally disjoint } a\text{–}b \text{ paths in } G\} = \kappa_{a,b}(G), \end{align*} which is Menger's theorem in the vertex, local form. [/step] [illustration:menger-case1-stitching]