The concepts of cuts in a network is a way to verify the Ford-Fulkerson algorithm and proof that the Max-Flow Min-Cut theorem.

You can review these topics:

Consider partitioning the nodes of a graph into two partitions, A and B such that s ∈ A and t ∈ B. This is called a cut. Any such partition places an upper bound on the maximum possible flow value since all the flow must pass from A to B at some point.

We can define an s-t cut as a partition (A, B) of the set of nodes (V), such that s ∈ A, and t ∈ B. The capacity of a cut is given as c(A, B) which is the sum of all the capacities of all edges out of A. This can be written as:

c(A, B) = ∑_{e out of A} c_{e}

This can be formulated into a formal statement as:

Let f be any s-t flow and (A, B) be any s-t cut. Then v(f) = f^{out}(A) = f^{in}(A)

This means that the values of the flow can be found by taking the total amount of flow that leaves A minus the amount that comes back into A.

**Proof: **

We know that v(f) = f^{out}(s): that is values of the flow is same as value of flow out of the source

Also, fin(s) = 0: since there is no incoming node to s. Therefor we can write

v(f) = f_{out}(s) – f^{in}(s)

Considering the partition A, every node in A is an internal node other than s, we can then write:

f^{out}(v) – f^{in}(v) = 0 for all these internal nodes. The can be written in the form:

v(f) = ∑_{v∈A}f^{out}(v) – f^{in}(v)

To be continued…