(a) Let $G$ be a flow network with capacities $c_{i j}$ on the edges. Explain the maximum flow problem on this network defining all the notation you need.

(b) Describe the Ford-Fulkerson algorithm for finding a maximum flow and state the max-flow min-cut theorem.

(c) Apply the Ford-Fulkerson algorithm to find a maximum flow and a minimum cut of the following network:

(d) Suppose that we add $\varepsilon>0$ to each capacity of a flow network. Is it true that the maximum flow will always increase by $\varepsilon$ ? Justify your answer.