图割

图割（cut）由一个顶点集合及其补集之间的全部边组成。对无向图 $G=(V,E)$ 和 $S\subseteq V$，记 $$\delta (S)=\{uv\in E:u\in S,v\in V\setminus S\}.$$ 把顶点分成两侧后，哪些边属于割就被完全确定；不能只从跨边中任取几条仍称它为同一顶点划分的割。一般讨论断开图的非平凡割时，两侧都要求非空。

例如，顶点为 $a,b,c,d,e$、边为 $ab,ac,bc,cd,de$。取 $S=\{a,b,c\}$，唯一跨边为 $cd$；取 $T=\{a,c\}$，跨边则为 $ab,bc,cd$。同一图的割可能大小不同，最小割只是在这些割中优化得到的一个数值或对象。

边cd的端点分处两侧，因此属于割；三角形内部边和框外de均不属于割。

割断开的对象与最小性的区别

删除 $\delta (S)$ 后不会有从 $S$ 到补集的路径。因为任何这样的路径都有一个第一次离开 $S$ 的步骤，该步必使用一条跨边，然而全部跨边已经删除。这个证明也说明：原图中任何连接两侧的路径，都至少穿过割一次。

割未必是删边断开图的最小集合。主例的 $\delta (\{a,c\})=\{ab,bc,cd\}$ 是一个割，但只删其中 $cd$ 就足以断开整张图，所以它不是按包含关系极小的断图边集。这样的极小非空割常称为键（bond）。“极小”表示无法再删去集合中的某些边而仍保有断图功能；“最小”表示在所有候选中大小或权重达到全局最小值。

在连通图中，非空割 $\delta (S)$ 是键，当且仅当两侧诱导子图都连通。若两侧连通，保留任意一条跨边就会把两侧连接成一体，所以每条跨边都不可少。反之，若例如 $G[S]$ 有多个分量，取其中一个分量 $C$；连通性保证每个这样的分量都有跨出 $S$ 的边，于是 $\delta (C)$ 是 $\delta (S)$ 的非空真子集，也能断开图，违背极小性。

度数总和中的边界项

记 $e(S)$ 为两个端点都在 $S$ 内的边数。对 $S$ 内顶点的度求和，每条内部边计两次，每条跨边计一次，而完全在外部的边不计，因此 $$\sum _{v\in S}\mathrm{deg}(v)=2e(S)+\mathrm{\#}\delta (S).$$ 主例中 $S=\{a,b,c\}$ 的度数和为 $2+2+3=7$，内部三条边贡献六，余下一就是跨边 $cd$。若取 $T=\{a,c\}$，度数和为五，内部边 $ac$ 贡献二，所以割大小为三。

变式。 取 $U=\{c,d\}$。其度数和为 $3+2=5$，内部只有 $cd$ 一条边，故割大小为三；实际跨边为 $ac,bc,de$。如果把内部边也算进割，会与这一恒等式冲突。

路径与环穿过割的奇偶性

沿一条游走，每次穿过割，当前位置就从一侧切换到另一侧。起点和终点异侧时，穿越次数为奇数；同侧时为偶数。特别地，每个环与任意割相交的边数都是偶数，因为走完环回到原侧。

这是一个逐步可验证的结论：给 $S$ 内顶点记零，外部顶点记一；每条跨边使记号翻转，内部边则不改变记号。首尾记号之差模二，正等于翻转次数模二。主例的三角形 $abc$ 与割 $\delta (\{a,c\})$ 恰好相交于 $ab,bc$ 两条边，符合偶数结论。环可以多次进出同一侧，但不可能只穿一次。

对任意两个顶点集 $S,T$，还可逐边证明 $$\delta (S\mathrm{△}T)=\delta (S)\mathrm{△}\delta (T),$$ 其中 $\mathrm{△}$ 为对称差，即属于其中恰好一个集合的元素。若边两端分别为 $u,v$，它是否穿过 $S$ 由 ${\mathrm{𝟏}}_S(u)+{\mathrm{𝟏}}_S(v)$ 的模二值确定；把 $S,T$ 的值相加模二，恰对应 $S\mathrm{△}T$。所以割集合在“对称差”运算下封闭，这就是割空间的基础；系数在这里取模二，和通常的边权加法不同。

有向割与容量

在有向图中必须区分离开一侧的边 ${\delta }^{+}(S)$ 与进入一侧的边 ${\delta }^{-}(S)$。若每条有向边容量为 $c_e\ge 0$，从 $S$ 内的源点向外部汇点运输流量时，割容量通常定义为 $$c({\delta }^{+}(S))=\sum _{e\in {\delta }^{+}(S)}{c}_e.$$ 对内部顶点流量守恒求和，内部边的流入和流出相互抵消，留下净流出等于“跨出流量减跨入流量”。由于跨入流量非负，净流出不超过跨出容量。这给出任意可行流均不超过任意源汇割容量的上界；它只证明弱对偶，不单独证明最大流最小割相等。完整相等定理见网络流与最大流最小割。