[proofplan] Each direction reduces to the local form of Menger's theorem. The forward implication is immediate: any vertex separator $S$ of $G$ disconnects some pair $a, b \notin S$, and the $k$ internally disjoint $a$–$b$ paths guaranteed by hypothesis must each meet $S$ at a distinct internal vertex, forcing $|S| \geq k$. For the converse, fix distinct $a, b \in V(G)$ and split on adjacency. If $a \not\sim b$, every $a$–$b$ separator is a global separator of $G$, so $\kappa_{a,b}(G) \geq \kappa(G) \geq k$ and the local form applies in $G$. If $a \sim b$, we delete the edge $\{a,b\}$ to form $G' := G - \{a,b\}$, prove $\kappa(G') \geq k - 1$ by showing every vertex separator of $G'$ can be enlarged by at most one vertex to a separator of $G$, apply the local form in $G'$ to obtain $k - 1$ internally disjoint $a$–$b$ paths (for $k \geq 2$), and close the family by adjoining the single-edge path $a, b$; the case $k = 1$ is immediate from the edge $\{a, b\}$ alone. [/proofplan] [step:Deduce $\kappa(G) \geq k$ from the existence of $k$ internally disjoint paths between every pair] Assume every pair of distinct vertices $a, b \in V(G)$ admits $k$ internally disjoint $a$–$b$ paths. Let $S \subseteq V(G)$ be a vertex separator of $G$: by definition $G - S$ is disconnected, so there exist distinct $a, b \in V(G) \setminus S$ lying in different components of $G - S$. Every $a$–$b$ path in $G$ must therefore pass through some vertex of $S$, and since $a, b \notin S$, this vertex is internal. By hypothesis there are $k$ internally disjoint $a$–$b$ paths $P_1, \ldots, P_k$ in $G$. Each $P_i$ meets $S$ at an internal vertex $s_i$, and internal disjointness forces the $s_i$ to be pairwise distinct: a common $s_i = s_j$ with $i \neq j$ would be an internal vertex shared by $P_i$ and $P_j$. Hence \begin{align*} |S| \geq |\{s_1, \ldots, s_k\}| = k. \end{align*} Taking the infimum over separators $S$ gives $\kappa(G) \geq k$. [guided] We must show that every vertex separator $S$ of $G$ has $|S| \geq k$. The strategy: find a pair of vertices for which $S$ blocks every path between them, then use the hypothesis to exhibit $k$ internally disjoint paths joining this pair; each path must be blocked by an internal vertex in $S$, and disjointness forces these blocking vertices to be distinct, giving $|S| \geq k$. By definition of a vertex separator, $G - S$ is disconnected, so we can choose distinct $a, b \in V(G) \setminus S$ in different components of $G - S$. Both endpoints lie outside $S$, so in any $a$–$b$ path only internal vertices could lie in $S$; on the other hand, since $a$ and $b$ are disconnected in $G - S$, every $a$–$b$ path in $G$ must visit some vertex of $S$. Combining: every $a$–$b$ path in $G$ contains an internal vertex in $S$. Apply the hypothesis to the pair $(a, b)$: there exist $k$ internally disjoint $a$–$b$ paths $P_1, \ldots, P_k$ in $G$. Each $P_i$ has an internal vertex $s_i \in S$. Why are the $s_i$ pairwise distinct? If $s_i = s_j$ for some $i \neq j$, then this single vertex is internal to both $P_i$ and $P_j$, contradicting internal disjointness. Therefore \begin{align*} |S| \geq |\{s_1, \ldots, s_k\}| = k. \end{align*} Since $S$ was an arbitrary vertex separator, $\kappa(G) \geq k$. [/guided] [/step] [step:Fix an arbitrary pair of distinct vertices and split the converse on adjacency] For the converse, assume $G$ is $k$-connected. Since $\kappa(G) \geq k$ and $\kappa(G) \leq |V(G)| - 1$, we have $|V(G)| \geq k + 1$. Fix distinct vertices $a, b \in V(G)$. We must produce $k$ internally disjoint $a$–$b$ paths in $G$. Split into \begin{align*} \text{Case A:} \quad a \not\sim b \text{ in } G, \qquad \text{Case B:} \quad a \sim b \text{ in } G. \end{align*} [/step] [step:Apply the local form directly when $a \not\sim b$] Assume $a \not\sim b$. We claim $\kappa_{a,b}(G) \geq k$, where $\kappa_{a,b}(G)$ denotes the minimum size of an $a$–$b$ vertex separator in $G$. Let $T \subseteq V(G) \setminus \{a, b\}$ be an $a$–$b$ separator: $a$ and $b$ lie in different components of $G - T$. Then $G - T$ is disconnected, so $T$ is a vertex separator of $G$ in the global sense, whence $|T| \geq \kappa(G) \geq k$. Infimising over $a$–$b$ separators gives $\kappa_{a,b}(G) \geq k$. Since $G$ is connected and $a, b$ are distinct non-adjacent vertices with $\kappa_{a,b}(G) \geq k$, the [local form of Menger's theorem](/theorems/2021) produces $\kappa_{a,b}(G) \geq k$ internally disjoint $a$–$b$ paths in $G$; discarding surplus paths leaves exactly $k$. [guided] In Case A the idea is to apply the local form of Menger directly in $G$. The local form requires: \begin{enumerate} \item $G$ is connected — holds because $\kappa(G) \geq k \geq 1$; \item $a, b$ are distinct non-adjacent vertices — holds by hypothesis and the case assumption; \item $\kappa_{a,b}(G) \geq k$ — to be verified. \end{enumerate} For (3), let $T \subseteq V(G) \setminus \{a, b\}$ be any $a$–$b$ separator: $a$ and $b$ lie in different components of $G - T$. In particular $G - T$ is disconnected, so $T$ is a vertex separator of $G$, hence $|T| \geq \kappa(G) \geq k$. Taking the infimum over all $a$–$b$ separators gives $\kappa_{a,b}(G) \geq k$. The [local form of Menger's theorem](/theorems/2021) now yields $\kappa_{a,b}(G)$ internally disjoint $a$–$b$ paths in $G$; since $\kappa_{a,b}(G) \geq k$, we select $k$ of them and discard the rest. This closes Case A. [/guided] [/step] [step:Dispose of Case B for $k = 1$ by taking the edge as the single path] Assume $a \sim b$ and $k = 1$. The edge $\{a, b\} \in E(G)$, viewed as the two-vertex path with vertex sequence $a, b$, is an $a$–$b$ path in $G$ with no internal vertices. A family consisting of this single path is vacuously a family of $1$ internally disjoint $a$–$b$ paths. [guided] When $k = 1$, the converse asserts that some $a$–$b$ path exists — which, since $a \sim b$, follows immediately from the edge $\{a, b\} \in E(G)$. The two-vertex path with vertex sequence $a, b$ has no internal vertices and is vacuously internally disjoint from any other path. We isolate $k = 1$ as a separate step because the main reduction below passes to $G' = G - \{a, b\}$ and applies the local form of Menger in $G'$, which requires $G'$ to be connected — a property we deduce from $\kappa(G') \geq k - 1 \geq 1$ only when $k \geq 2$. [/guided] [/step] [step:Prove $\kappa(G - e) \geq \kappa(G) - 1$ for every edge $e$] Assume $a \sim b$ and $k \geq 2$. Let $G' := G - \{a, b\}$ denote the graph obtained from $G$ by deleting the edge $\{a,b\}$ (retaining both endpoints). We establish the following lemma. [claim:For every edge $e \in E(G)$, $\kappa(G - e) \geq \kappa(G) - 1$] [proof] Let $e = \{a, b\}$ and set $G' = G - e$; note $V(G') = V(G)$ and $E(G') = E(G) \setminus \{e\}$. We show that every vertex separator $T$ of $G'$ satisfies $|T| \geq \kappa(G) - 1$. Let $T \subseteq V(G')$ be a vertex separator of $G'$: $G' - T$ is disconnected. We consider two cases according to whether $T$ contains an endpoint of $e$. \textbf{Case (i): $a \in T$ or $b \in T$.} The edge $e$ has an endpoint in $T$, so $e$ is not an edge of $G - T$. Hence $G - T$ and $G' - T$ have the same edge set on the same vertex set, i.e. $G - T = G' - T$. The latter is disconnected, so $T$ is a vertex separator of $G$, giving $|T| \geq \kappa(G) \geq \kappa(G) - 1$. \textbf{Case (ii): $a, b \notin T$.} Then $e \in E(G - T)$, and $G - T$ is obtained from $G' - T$ by adding the single edge $e = \{a,b\}$. \emph{Subcase (ii.a): $a$ and $b$ lie in the same component of $G' - T$.} Adding the edge $e$ within a component does not change the component structure, so $G - T$ has the same components as $G' - T$, hence is disconnected. Therefore $T$ is a vertex separator of $G$ and $|T| \geq \kappa(G) \geq \kappa(G) - 1$. \emph{Subcase (ii.b): $a$ and $b$ lie in different components of $G' - T$.} Let $C_a$ and $C_b$ denote the components of $G' - T$ containing $a$ and $b$ respectively. We claim that either $T \cup \{a\}$ or $T \cup \{b\}$ is a vertex separator of $G$ of size $|T| + 1$, or $|V(G)| = |T| + 2$; in all cases $|T| \geq \kappa(G) - 1$. Consider $T^* := T \cup \{a\}$, of size $|T| + 1$. Since $a \in T^*$, the edge $e$ has an endpoint in $T^*$, so $G - T^* = G' - T^*$. The graph $G' - T^*$ is obtained from $G' - T$ by deleting the vertex $a$; its vertex set is $V(G') \setminus T^* = (C_a \setminus \{a\}) \cup C_b \cup \bigcup_{C \neq C_a, C_b} C$, where the last union ranges over remaining components of $G' - T$. The components $C_b$ and any $C \neq C_a$ survive intact and are pairwise disconnected in $G' - T^*$. If $|V(C_a)| \geq 2$, then $C_a \setminus \{a\}$ is nonempty and disjoint from $C_b$ in $G' - T^*$, so $G - T^* = G' - T^*$ is disconnected and $T^*$ is a vertex separator of $G$: $|T| + 1 \geq \kappa(G)$, i.e. $|T| \geq \kappa(G) - 1$. If $|V(C_a)| = 1$, i.e. $C_a = \{a\}$, then consider the symmetric choice $T^{**} := T \cup \{b\}$. By the same argument applied with the roles of $a$ and $b$ swapped, $T^{**}$ is a vertex separator of $G$ provided $|V(C_b)| \geq 2$. If $|V(C_a)| = |V(C_b)| = 1$, then $C_a = \{a\}$ and $C_b = \{b\}$. If $G' - T$ had a further component beyond $C_a$ and $C_b$, then $T^* = T \cup \{a\}$ still leaves $C_b$ and that further component both nonempty and disconnected, so $T^*$ separates $G$. If $G' - T$ has only the two components $\{a\}$ and $\{b\}$, then $V(G') = T \cup \{a, b\}$, so $|V(G)| = |V(G')| = |T| + 2$. Combined with $|V(G)| \geq \kappa(G) + 1$, this gives $|T| + 2 \geq \kappa(G) + 1$, i.e. $|T| \geq \kappa(G) - 1$. In every subcase $|T| \geq \kappa(G) - 1$. \medskip Thus every vertex separator of $G'$ has size at least $\kappa(G) - 1$, so $\kappa(G') \geq \kappa(G) - 1$. [/proof] [/claim] Applied to $G$ and the edge $e = \{a, b\}$, the lemma gives $\kappa(G') \geq \kappa(G) - 1 \geq k - 1 \geq 1$, so in particular $G'$ is connected. [guided] When $a \sim b$ we cannot apply the local form of Menger in $G$: the local form requires non-adjacent endpoints, and when $\{a,b\} \in E(G)$ there is no $a$–$b$ vertex separator at all — the edge itself is an $a$–$b$ path with no internal vertex, so no amount of internal-vertex deletion can destroy it. The standard trick is to delete the edge: $G' := G - \{a, b\}$ makes $a$ and $b$ non-adjacent while preserving all other structure. The cost is that connectivity may drop. How far? The lemma says: by at most $1$. \textbf{Why edge-deletion drops connectivity by at most one.} Let $T$ be any vertex separator of $G'$. We show $|T| \geq \kappa(G) - 1$ by producing a vertex separator of $G$ of size at most $|T| + 1$. The vertex sets of $G$ and $G'$ are equal, and their edge sets differ only by $e = \{a, b\}$. So $G - T$ and $G' - T$ have the same vertex set $V(G) \setminus T$, and their edge sets differ by at most the single edge $e$. \emph{If $a \in T$ or $b \in T$:} the edge $e$ has an endpoint in $T$, hence is absent from both $G - T$ and $G' - T$. So $G - T = G' - T$ is disconnected, and $T$ itself separates $G$. Thus $|T| \geq \kappa(G)$, which is stronger than needed. \emph{If $a, b \notin T$:} the edge $e$ is present in $G - T$ but absent from $G' - T$. The graph $G - T$ is obtained from $G' - T$ by adding the single edge $e$. Adding one edge merges at most two components, so the number of components decreases by $0$ or $1$. If $a$ and $b$ are already in the same component of $G' - T$, adding $e$ does not change the component structure: $G - T$ is disconnected and $T$ separates $G$. If $a$ and $b$ are in different components $C_a$ and $C_b$ of $G' - T$, then the edge $e$ merges $C_a$ and $C_b$ in $G - T$. Now consider $T^* := T \cup \{a\}$, which has size $|T| + 1$. Deleting $a$ re-severs the merge, because $G - T^* = G' - T^*$ (the edge $e$ is absent once $a$ is removed), and $G' - T^*$ differs from $G' - T$ only by removing $a$. So $G' - T^*$ has as components: $C_a \setminus \{a\}$ (possibly empty), $C_b$ (intact), and all other components of $G' - T$ (intact). Provided $C_a \setminus \{a\}$ is nonempty or there is some component of $G' - T$ other than $C_a$ and $C_b$, the graph $G - T^*$ is disconnected and $T^*$ is a separator of $G$: $|T| + 1 \geq \kappa(G)$, i.e. $|T| \geq \kappa(G) - 1$. The only remaining possibility is $C_a = \{a\}$, $C_b = \{b\}$, and $G' - T$ has no other components. Then $V(G') = T \cup \{a, b\}$, so $|V(G)| = |T| + 2$. Combining with $|V(G)| \geq \kappa(G) + 1$ (the general inequality for any graph with a vertex separator), we get $|T| + 2 \geq \kappa(G) + 1$, i.e. $|T| \geq \kappa(G) - 1$. In every case $|T| \geq \kappa(G) - 1$, as claimed. Applied with $\kappa(G) \geq k \geq 2$, the lemma gives $\kappa(G') \geq k - 1 \geq 1$, so $G'$ is connected. [/guided] [/step] [step:Apply the local form in $G'$ and adjoin the edge-path $a, b$] Continue with $k \geq 2$ and $a \sim b$, so $G' = G - \{a,b\}$ is connected and $\kappa(G') \geq k - 1$. By construction $\{a, b\} \notin E(G')$, so $a$ and $b$ are distinct non-adjacent vertices of $G'$. We claim $\kappa_{a,b}(G') \geq k - 1$. Let $T' \subseteq V(G') \setminus \{a, b\}$ be an $a$–$b$ separator in $G'$: $a$ and $b$ lie in different components of $G' - T'$, so $G' - T'$ is disconnected and $T'$ is a vertex separator of $G'$. Hence $|T'| \geq \kappa(G') \geq k - 1$, and infimising gives $\kappa_{a,b}(G') \geq k - 1$. By the [local form of Menger's theorem](/theorems/2021), applied to the connected graph $G'$ with distinct non-adjacent vertices $a, b$ and $\kappa_{a,b}(G') \geq k - 1$, there exist $k - 1$ internally disjoint $a$–$b$ paths $P_1, \ldots, P_{k-1}$ in $G'$. Define $P_k$ to be the two-vertex path with vertex sequence $a, b$, traversing the edge $\{a, b\} \in E(G)$. Since $P_k$ has no internal vertices, it is vacuously internally disjoint from every $P_i$ with $1 \leq i \leq k - 1$. The paths $P_1, \ldots, P_{k-1}$ are subgraphs of $G'$, so they do not use the edge $\{a, b\}$, and their pairwise internal disjointness in $G'$ transfers to $G$ unchanged. Therefore $P_1, \ldots, P_{k-1}, P_k$ are $k$ internally disjoint $a$–$b$ paths in $G$. [guided] We now have everything needed to apply the local form in $G'$: the graph $G'$ is connected (by the previous step), the vertices $a$ and $b$ are distinct and non-adjacent in $G'$ (we deleted the edge $\{a, b\}$), and $\kappa_{a,b}(G') \geq k - 1$. Why $\kappa_{a,b}(G') \geq k - 1$? Any $a$–$b$ separator $T'$ of $G'$ disconnects $a$ from $b$ in $G' - T'$, so in particular $G' - T'$ is disconnected and $T'$ is a global vertex separator of $G'$; hence $|T'| \geq \kappa(G') \geq k - 1$ by the previous step's lemma. The [local form of Menger's theorem](/theorems/2021) now yields $k - 1$ internally disjoint $a$–$b$ paths $P_1, \ldots, P_{k-1}$ in $G'$. These are the first $k - 1$ paths of the desired family. The $k$-th path is the edge $\{a, b\}$ itself, traversed as the two-vertex path with vertex sequence $a, b$; call it $P_k$. The key property of $P_k$ is that it has no internal vertices, which makes internal disjointness with every other path automatic — internal disjointness is a condition on the shared internal vertices of two paths, and one of them having none makes the intersection vacuously empty. We must also check that the $P_i$ for $i < k$ remain valid internally disjoint $a$–$b$ paths when viewed in $G$ (not just $G'$). A path is a sequence of vertices and edges, and the $P_i$ as subgraphs of $G'$ are subgraphs of $G$ (since $V(G') = V(G)$ and $E(G') \subseteq E(G)$). Their internal vertices lie in $V(G') \setminus \{a, b\} = V(G) \setminus \{a, b\}$, and internal disjointness is a statement about shared internal vertices, which is unaffected by the ambient graph. Therefore $P_1, \ldots, P_{k-1}, P_k$ are $k$ internally disjoint $a$–$b$ paths in $G$, closing Case B for $k \geq 2$. [/guided] [/step] [step:Combine the two cases to complete the converse] Case A handles $a \not\sim b$; the $k = 1$ step and the $k \geq 2$ step together handle $a \sim b$. In every situation we have produced $k$ internally disjoint $a$–$b$ paths in $G$. Since $a, b$ were arbitrary distinct vertices, every pair admits $k$ such paths. Together with the forward direction, this proves that $G$ is $k$-connected if and only if every pair of distinct vertices admits $k$ internally disjoint $a$–$b$ paths. [/step]