Menger 定理

若 $S$ 能截断所有 $s$–$t$ 路，那么每条路径都必须经过 $S$ 中至少一个点。内部顶点不交的路径不能使用同一个截断点，因此任意这类路径族的大小都不超过 $|S|$。这只证明了

Menger 定理的内容是反向不等式：无论图的路径怎样纠缠，都能找到与最薄弱顶点瓶颈同样多的独立通道。

“通道”和“故障点”是同一组合结构的两种证书。给出 $k$ 条内部不交路径，可以证明少于 $k$ 个内部顶点无法全部截断；给出大小为 $k$ 的分离集，则证明不可能存在第 $k+1$ 条独立路径。等式保证总有一对最优证书在同一个数值相遇。

顶点拆分把点版化为 最大流最小割定理理路最大流最小割定理Max-flow min-cut theorem以净跨割恒等式和残量可达集证明最大流等于最小割，并给出独立可检查的最优性证书。。对每个内部顶点 $v\notin \{s,t\}$ 建立 $v_{\mathrm{in}}$ 与 $v_{\mathrm{out}}$，加入容量为 $1$ 的弧

每条无向边 $\{u,v\}$ 替换为两个方向的弧，从 $u$ 的 out 端连到 $v$ 的 in 端，反向也同样连接，并赋整数容量 $M=|V|+1$；$s,t$ 不拆分。大容量弧表达“原图边不是点版中的瓶颈”，单位容量弧则保证每个内部顶点最多承载一单位流。

任意 $k$ 条内部顶点不交路径都会给出值为 $k$ 的整数流。反过来，取从零流增广得到的整数最大流；简单源汇增广路不会给进入 $s$ 或离开 $t$ 的原弧加流，所以去掉环后可分解成 $s$–$t$ 路；单位顶点弧保证这些路径内部不共享顶点。由于 $s,t$ 不相邻，删掉 $V\setminus \{s,t\}$ 总能分离端点，所以存在容量小于 $M$ 的割；最小割不会切任何大容量原边弧，只会切若干 $v_{\mathrm{in}}\to v_{\mathrm{out}}$。这些 $v$ 恰组成原图的顶点分离集。流的整数性和最大流最小割于是给出两边相等。

在由 $s-a-t$ 与 $s-b-t$ 两条路径组成的图中，删去 $a$ 仍留下经 $b$ 的路，删去 $b$ 也一样；必须同时删去 $\{a,b\}$。两条给定路径内部不交，所以最大路数和最小分离集大小都为 $2$。再加入边 $a-b$ 会增加绕行方式，却不会产生第三个可独占的内部顶点，数值仍为 $2$。

点版排除相邻端点，是因为直接边 $st$ 没有内部顶点，任何禁止删除 $s,t$ 的顶点集都无法截断它。对简单图的一种明确扩展是先删去边 $st$：若 $\nu$ 表示内部不交路径最大数，$\kappa$ 表示最小端点外分离集大小，那么除直接边外的路径由 $G-st$ 中的 Menger 定理计算，因此

也可以改用允许分离集碰到端点的集合版定理。无论采用哪种约定，都必须在公式前说明；不能一边保留直接边，一边仍把右侧写成不存在的端点外顶点割。

边版没有这个困难，因为删边集可以直接包含 $st$。其流证明无需拆顶点：把每条无向边换成两个反向的容量 $1$ 弧。若同一无向边的两个方向同时有流，先等量抵消，保持守恒与净流值；再去掉环并分解最优整数流，就得到不重复使用任何无向边的源汇路径。一个有向割对每条跨割无向边只计其中一个向外弧，所以最小容量割恰是最小删边数。对有向图也有相应 Menger 定理，但路径方向和分离条件都要按有向可达性解释。

连通性理路图连通性Graph connectivity用顶点间是否存在路径定义无向图的连通性，并由此划分连通分量。只询问是否存在一条路，Menger 定理把它提升为可量化的鲁棒性。一个至少有 $k+1$ 个顶点的图是 $k$-顶点连通的，当且仅当任意两点之间都有 $k$ 条内部顶点不交路径；相应地，$k$-边连通由 $k$ 条边不交路径刻画。割点与桥理路割点与桥Cut vertex and bridge删除后增加连通分量数的顶点或边。分别是数值降到 $1$ 时最直接的瓶颈。

在网络中，路径族是冗余路由证书，分离集是最小失效证书。点拆分不仅证明定理，也把“节点容量、节点故障”问题转成标准流实例，使路径和割可由同一算法框架求出。耳分解、连通度算法以及许多图的结构定理，都以这条局部最大—最小等式为基础。