algorithmgraph-algorithmnetwork-flow

Why is the global min cut cardinality less than the degree of every vertex for network flows


I get that min-cut equals to max flow. But why does every node has to have a degree larger than the cardinality of global min-cut for it to be valid


Solution

  • For every node, cutting that node from the rest of the graph produces a cut of size equal to the degree of that node, hence the global min cut can be no larger.