Problem $3.$ Max Flow $(10$ points$)$

One greedy approach to Max Flow would repeatedly find a path from the source $s$ to the sink $t.$ If

the path exists, then find the minimum$-$capacity edge on that path, increase flow on all edges of the

path, and then remove those edges from consideration.

$($a$)$ Give an example of a directed graph, with capacities on each edge, for which that Greedy

choice would not find an optimal solution.

Solution:

$($b$)$ In your graph above, what solution would the Greedy approach give you? If there are multiple

solutions depending on which path you start with, please include all of the outcomes.

Solution:

$($c$)$ What would the optimal solution be for your example?

Solution: