连通性：分隔集与 Menger 定理
一张图「有多结实」可以从两个相反的方向度量：拆——至少删掉几个顶点才能把 s 与 t 断开；连——最多能在 s 与 t 之间铺几条互不踩点的路。Menger 定理断言这两个数恰好相等。本页在一张固定图上选定
s、t，逐条标出一组最多的内部不相交路，再高亮一个大小恰好相等的最小分隔集，把这个对偶直接摆在眼前。
s-t 分隔集 (separator): 一组顶点 S（不含 s、t），从图中删去 S 后 s 与 t 不再连通。
内部不相交 (internally vertex-disjoint) 的 s-t 路： 一组 s 到 t 的路，两两之间除端点 s、t 外不共享任何顶点（因而也不共享边）。
Menger 定理（顶点形式）
设 s、t 是图中不相邻的两个顶点。则
最小 s-t 分隔集大小 = 最大内部不相交 s-t 路数目
一侧总不超过另一侧是容易的：每条不相交路都必须被分隔集「截断」一次，而不同的路被截在不同顶点上（它们内部不共享顶点），所以分隔集至少要有「路数」那么大。Menger 的内容是反方向——这个下界能取到。
怎么算出来的： 把每个内部顶点 v 拆成
一条容量 1 的弧（限制「每点最多被一条路用一次」），原图每条边给单位容量，再求 s 到 t 的最大流。最大流值 = 不相交路数；最小割里被切断的那些「拆点弧」对应的顶点，就构成一个最小分隔集。这正是 Menger 定理 =
最大流最小割定理在单位容量、顶点版本下的特例。
从局部到全局——k-连通： 若图至少有 k+1 个顶点，且删去任意少于 k 个顶点后仍连通，就称它是 k-连通 (k-connected)。等价地（Menger 的全局形式）：任意两个顶点之间都存在 k 条内部不相交的路。连通度
κ(G) 就是使图变得不连通（或退化为单点）所需删去的最少顶点数，亦即最大的 k 使图 k-连通。
Mader 定理： 高连通子图无法靠「整体平均度高」直接保证，但可以靠「足够高的平均度」逼出来。Mader 证明：若一张图的平均度满足
，则它必含一个 (k+1)-连通的子图。换言之，边足够稠密（即便边分布不均）也无法避免局部出现高连通的子结构——这类「稠密 ⟹ 含强连通子结构」的结果是极值图论里把平均度翻译成连通度的桥梁。