边连通度

边连通度（edge connectivity）是使一个连通无向图变得不连通所需删除的最少边数，记为 $\lambda (G)$。它衡量图的连接对边失效的承受能力。本文讨论至少两个顶点的有限无向简单图；对已经不连通的图取 $\lambda (G)=0$。

一条桥的删除就能切断图，所以有桥的连通图边连通度为一；环的边连通度为二，因为删任意一条边仍有一条贯穿全部顶点的路径，删两条不同边则会断开。与顶点连通度相比，这里删除的对象是边，边两端顶点均保留。

从删边改写为最小割

对非空真顶点子集 $S\subset V$，令 $$\delta (S)=\{uv\in E:u\in S,v\notin S\}$$ 为跨越 $S$ 与其补集的图割。则 $$\lambda (G)=\underset{\varnothing \ne S⊊V}{min}\mathrm{\#}\delta (S).$$

证明。 删除 $\delta (S)$ 后，两侧均有顶点却没有跨边，不可能有连接两侧的路径，因此任何这样的割都是一种删边断图方案，给出“删边最小数不大于割最小数”。反过来，若删除边集 $F$ 后断开，取结果图的一个连通分量顶点集 $S$。原图中所有跨越两侧的边都必已被删除，故 $\delta (S)\subseteq F$，于是割最小数不大于 $\mathrm{\#}F$。两向取最小值得到等式。

这使上界和下界具有不同的检查方式：给出一个小割得到上界；证明每个非平凡割都足够大得到下界。

五顶点轮图的全部割下界

取外围四环 $a,b,c,d,a$，再加中心 $o$ 及四条辐射边。单独取 $S=\{a\}$ 时，跨边恰为 $ab,ad,ao$，所以 $\lambda (G)\le 3$。

删除这三条跨边会使a孤立，给出边连通度至多三的证据。

为证明没有一边或两边割，考虑任意非平凡割。交换两侧不改变跨边，因此可令中心在补集一侧；$S$ 就是非空外围顶点集。设 $k=\mathrm{\#}S$，其中 $1\le k\le 4$。每个所选外围点有一条通向中心的辐射边，所以已有 $k$ 条跨边。

若 $k=1$，外围环再贡献两条边，割大小为三。若 $k=2$，相邻两点的环边界有两条，对顶两点的环边界有四条，因此割大小至少四。若 $k=3$，未选外围点的两条环边均跨界，割大小为五。若 $k=4$，没有外围跨边，但四条辐射边全部跨界，割大小为四。由此所有割大小至少三，结合上界得到 $$\lambda (G)=3.$$ 这是一份覆盖全部割的证明，无需逐一列出所有非空真子集。

最小度、桥与树

选择一个最小度顶点 $v$，删除它的全部关联边便使它孤立，故 $$\lambda (G)\le \delta (G).$$ 这里 $\delta (G)$ 是最小度，与表示边割的 $\delta (S)$ 使用了同一个传统字母，括号中的对象可区分它们。图的最小度为零时本来不连通，上式也相容。

反向一般不成立。用一条边连接两个三角形，两端连接点的度为三，其余点的度为二，所以最小度是二；中间连接边却是桥，边连通度为一。两侧各自有绕行，并不能补上两区域之间仅有的一条连接。

对至少两顶点的树，每条边都是桥，所以边连通度为一。证明是：删一条边若两端仍有另一条路径，将这条路径与被删边合起来会构成环，与树无环矛盾。这也说明在连通图中，边连通度为一当且仅当存在桥。

变式与加边的影响

变式。 在主例中删除辐射边 $oa$。顶点 $a$ 度为二，所以边连通度至多二，边集 $\{ab,ad\}$ 确实使其孤立。另一方面，每条剩余边仍在某个环上：四条外围边都在外围四环上；辐射边 $ob,oc$ 在三角形 $obco$ 上，$od$ 在三角形 $ocdo$ 上。因此没有桥，删一条边不会断开，边连通度至少二。新值恰为二。

在固定顶点集上增加边，每个割的边数都不减，因此最小割大小也不减。若新边两端位于某个原最小割的同侧，这个割的大小保持原值；这时整体边连通度也保持原值。判断增加哪条连接能提升可靠性，需要检查所有达到最小值的割，而不仅是某一个局部度数。

边连通度只计边数。若每条边都有不同建设费用、容量或失效概率，需另行定义加权割或概率模型；把边数三解释为“三倍可靠”并无数学依据。