**Flow**

Let be a directed graph where every edge has a capacity . We are given two special vertices where is the source vertex and is the sink vertex. A flow in is defined as function where . Further for every node we have the following conservation property: . In other words for every vertex that is not the source or the sink, the net incoming flow is the same as the net outgoing flow.

The value of the flow is given by . We claim that . To see this consider a matrix where the rows are indexed by vertices and the columns are indexed by the edges. For any vertex and edge the entry is equal to either if and is equal to if . Otherwise the entries are 0. Note that the sum of the entries in a particular row gives us the net flow out of that vertex. Clearly the columns sum up to . Since the net flow for every vertex not equal to is the claim follows.

**s-t Cut**

An cut is a subset of edges such that has no directed path from to in . We claim that the maximum number of edge disjoint paths in is the same as the size of the minimum cut. Clearly the maximum is always less than the minimum. Menger’s theorem says that equality is attained, i.e. the maximum number of edge disjoint path is equal to the size of the minimum cut.

Thus our cut only consists of edges of the form and . Define a flow .

**Claim: **The maximum flow in any graph is less than or equal to the capacity of the minimum cut. The capacity of a cut is defined as .

**Proof: **Note that . For every we have . Let us add up all the vertices in . We get . However . Thus . This proves the claim.

Are the flow concepts not in our textbook? If so, are there other places we can look to find them?