meets the capacity constraint of as will never exceed the minimum capacity of some edge on p by definition of . Skew symmetry is explicitly stated as for each there is . Flow conservation is implied by skew symmetry. as for any p in for any p in will be positive or else the path will be incomplete. Suppose that some , then there is no path through in , so .
Once a path is augmented, it cannot be augmented again until its flow is reduced. An augmentation will always leave some . The edge then cannot appear again in some ; . Each augmentation deletes at least one edge from . The most extreme case is one such that each path p in is comprised of exactly one edge. Therefore, each augmentation must delete exactly one edge while only deleting exactly one path as the number of paths is .
26.2-9
The edge connectivity of an undirected graph is the minimum number k of edges that must be removed to disconnect the graph. For example, the edge connectivity of a tree is 1, and the edge connectivity of a cyclic chain of vertices is 2. Show how the edge connectivity of an undirected graph can be determined by running a maximum-flow algorithm on at most flow networks, each having vertices and edges.
meets 
as 
on p by definition of 
. Skew symmetry is 
there is 
. Flow conservation is implied by skew symmetry. 
as 
, then there is no path 
through 
.
can always be found by a sequence of at most 
augmenting paths.
. The edge 
. Each augmentation deletes 
.
flow networks, each having 
edges.