[proofplan] We establish the two directions of the equivalence separately. The easy direction is that edge-disjoint paths force the edge-connectivity to be large: if every pair admits $k$ edge-disjoint $a$–$b$ paths, then any $a$–$b$ edge cut must pierce each of the $k$ paths, giving an edge count of at least $k$. The harder direction invokes [Menger's Theorem (Edge Version, Local Form)](/theorems/2023) to extract $k$ edge-disjoint paths between any fixed pair from the hypothesis that every such pair has edge-connectivity at least $k$. The arguments are entirely parallel to the vertex version; the only subtleties are (i) passing between the global parameter $\lambda(G)$ and the local parameter $\lambda_{a,b}(G)$, and (ii) verifying that the hypothesis of the local form is met for arbitrary $a \neq b$. [/proofplan] [step:Recall the definition of $\lambda(G)$ and reduce to local edge-connectivity] Let $G$ be a connected graph. Recall that the **edge-connectivity** of $G$ is \begin{align*} \lambda(G) := \min\{|W| : W \subseteq E(G) \text{ disconnects } G\}, \end{align*} and the **local edge-connectivity** between distinct vertices $a, b \in V(G)$ is \begin{align*} \lambda_{a,b}(G) := \min\{|W| : W \subseteq E(G), \; a \text{ and } b \text{ lie in different components of } G - W\}. \end{align*} Every disconnecting edge set separates some pair of vertices, and every pair-separating edge set disconnects $G$, so \begin{align*} \lambda(G) = \min_{a \neq b} \lambda_{a,b}(G). \end{align*} In particular, $\lambda(G) \geq k$ if and only if $\lambda_{a,b}(G) \geq k$ for every pair of distinct vertices $a, b$. [guided] The global parameter $\lambda(G)$ bounds the edge-connectivity of the graph as a whole, while $\lambda_{a,b}(G)$ bounds it for a specific pair. We need to relate the two because the local form of Menger's theorem works with $\lambda_{a,b}(G)$, whereas the statement we are proving is about $\lambda(G)$. The equivalence $\lambda(G) = \min_{a \neq b} \lambda_{a,b}(G)$ is straightforward: an edge set disconnects $G$ if and only if there is some pair of vertices in different components of the complement, which is the same as saying the set separates that pair. Taking the minimum cut size over all pairs recovers the global edge-connectivity. Hence "$\lambda(G) \geq k$" and "$\lambda_{a,b}(G) \geq k$ for all pairs $a \neq b$" are two names for the same condition. This is the bridge we use to switch from the global statement to a local one that the local form of Menger's theorem can address. [/guided] [/step] [step:Forward direction — $k$ edge-disjoint paths imply every edge cut has size at least $k$] Suppose every pair of distinct vertices $a, b \in V(G)$ admits $k$ edge-disjoint $a$–$b$ paths. Fix any disconnecting set $W \subseteq E(G)$. Since $W$ disconnects $G$, there exist vertices $a, b$ in different components of $G - W$; in particular $a \neq b$, and $W$ is an $a$–$b$ edge separator (every $a$–$b$ walk in $G$ must use some edge of $W$). By hypothesis, there exist $k$ edge-disjoint $a$–$b$ paths $P_1, \ldots, P_k$ in $G$. Each $P_j$ is an $a$–$b$ walk in $G$, so each must contain at least one edge of $W$: \begin{align*} E(P_j) \cap W \neq \varnothing \quad \text{for each } j \in \{1, \ldots, k\}. \end{align*} Pick $w_j \in E(P_j) \cap W$ for each $j$. The $w_j$ are pairwise distinct because the $P_j$ are pairwise edge-disjoint, so $\{w_1, \ldots, w_k\} \subseteq W$ has size $k$. Therefore $|W| \geq k$. Since $W$ was an arbitrary disconnecting edge set, $\lambda(G) \geq k$. [guided] The forward direction is a counting argument: each edge-disjoint path must contain at least one edge of any cut, and since the paths are edge-disjoint, these cut-intersections produce distinct edges. So a cut of size $k-1$ or smaller cannot separate any vertex pair that admits $k$ edge-disjoint paths. Formally: if $W$ disconnects $G$, there is some pair $a, b$ in different components of $G - W$, so $W$ is an $a$–$b$ edge separator. The $k$ edge-disjoint $a$–$b$ paths $P_1, \ldots, P_k$ each cross $W$ at least once. Picking one crossing edge $w_j \in E(P_j) \cap W$ per path produces $k$ distinct elements of $W$ — distinct because edge-disjointness of the $P_j$ means they share no edges, so the chosen $w_j \in E(P_j)$ cannot coincide with any $w_{j'} \in E(P_{j'})$ for $j \neq j'$. Hence $|W| \geq k$. This bound holds for every disconnecting $W$, so $\lambda(G) \geq k$. [/guided] [/step] [step:Reverse direction — apply the local edge form of Menger's theorem to every pair] Conversely, suppose $\lambda(G) \geq k$. By the reduction in Step 1, this means $\lambda_{a, b}(G) \geq k$ for every pair of distinct vertices $a, b \in V(G)$. Fix any pair $a \neq b$. Every edge set $W \subseteq E(G)$ that separates $a$ from $b$ satisfies $|W| \geq \lambda_{a,b}(G) \geq k$. Since $G$ is connected by hypothesis and $a \neq b$, the hypotheses of [Menger's Theorem (Edge Version, Local Form)](/theorems/2023) are met: - $G$ is connected; - $a$ and $b$ are distinct vertices; - every $a$–$b$ edge separator has size at least $k$. Applying the local form produces $k$ edge-disjoint $a$–$b$ paths in $G$. Since the pair $a \neq b$ was arbitrary, this proves that every pair of distinct vertices in $G$ admits $k$ edge-disjoint $a$–$b$ paths, completing the proof. [guided] For the reverse direction we want: given $\lambda(G) \geq k$, produce $k$ edge-disjoint $a$–$b$ paths for every pair $a \neq b$. The only tool we have for producing such paths is the local form of Menger's theorem, so we need to check its hypotheses for every fixed pair. Fix $a \neq b$. The hypotheses of [Menger's Theorem (Edge Version, Local Form)](/theorems/2023) are: 1. $G$ is connected — this is a hypothesis of our theorem, so it transfers directly. 2. $a \neq b$ are vertices of $G$ — this is our choice. 3. Every edge set $W$ separating $a$ from $b$ has $|W| \geq k$. For (3): by Step 1, $\lambda(G) = \min_{x \neq y} \lambda_{x,y}(G)$, so $\lambda(G) \geq k$ forces $\lambda_{a,b}(G) \geq k$. By definition $\lambda_{a,b}(G)$ is the minimum size of an $a$–$b$ edge separator, so every such separator $W$ has $|W| \geq k$. All three hypotheses hold, so the local form yields $k$ edge-disjoint $a$–$b$ paths. Since $a \neq b$ was arbitrary, this holds for every pair, which is exactly the conclusion of our theorem. [/guided] [/step]