为什么全局最小割基数小于网络流的每个顶点的度数

Question

我知道最小切割等于最大流量。但是为什么每个节点的度都必须大于全局最小割的基数才能有效

Answer 1

对于每个节点，从图中的其余部分切割该节点会产生大小等于该节点度数的切割，因此全局最小切割不能更大。