163 students only: Find an input to the maximum flow problem, and a flow (not necessarily a maximum flow) for your input, with the following property: there exists a directed edge \(u\to v\) in your input, for which the capacity of \(u\to v\) in the residual graph is bigger than it is in your input.
265 students only: Let \(C\) denote the largest edge capacity in a given instance of the maximum flow problem. As a function of \(C\), what is the largest possible capacity that could appear on any edge in any residual graph for this problem?
Find a maximum flow problem whose integer solutions correspond to the maximum matchings of the bipartite graph shown below. How many different integer maximum flows does your graph have?
Suppose that, like your answer to the previous problem, a network has more than one integer maximum flow. Describe a way of combining two of these integer flows to produce a maximum flow for the same network in which some of the flow amounts are not integers.
Find a minimum cut for the flow network from your answer to question 2. How many cuts (with the source vertex on the first side and the destination vertex on the second side) does this network have? How many of these cuts are minimum cuts?