Lesson 4

Theorem. The size of the maximum matching in \(G\) equals the maximum flow in \(G'\).

Proof. In a network with integer capacities there always exists a maximum integer flow. Integer flows in network \(G'\) are in one-to-one correspondence with matchings in \(G\):

• from a flow one can construct a matching by taking all edges of the original graph along which flow goes;


• from a matching one can construct a flow by sending liquid through each matching edge and from it.