k-edge-connected graph

k-edge-connected graph）λ(G)是最小的边割集的大小，两个顶点u到v的局部边连通度λ(u, v)是u到v最小的边割集的大小，同样，局部边连通度是对称的。如果一个图的边连通度为k或更大，则称该图为k-边连通的。

k-edge-connected graph）。 对无源汇最小割问题加以推广，可以得到最小k割问题（英语：minimum k-cut），即将图分为至少k个子图的最小割问题。对于一个确定的k，这个问题可以在多项式时间内完成，虽然算法在k较大时并不理想。

graph（英语：And-inverter graph） 有向图 有向无环图 Propositional directed acyclic graph（英语：Propositional directed acyclic graph） 伪图 超图 Lightmap 翼边 Quad-edge（英语：Quad-edge） 路由表 符号表

对于一张图，若不存在大小为k − 1的点集或边集，使得从图中移除该集合后，图就变为非连通图，则称该图是k-点连通图（英语：k-vertex-connected graph）或k-边连通图（英语：k-edge-connected graph）。k-点连通图通常也简称k-连通图。 二分图（英語：bipartite graph

使用，这样与 χ ( G ) = k {\displaystyle \chi (G)=k} 矛盾。 任意一个 k {\displaystyle k} -色临界图均为 k − 1 {\displaystyle k-1} -邊連通（英语：k-edge-connected graph）的。 证明用到以下引理： 设