Problem : Recall that our invariant for the Ford-Fulkerson method included "$G_r$ is the residual capacity graph." We showed in class that that part of the invariant is maintained for the edges $(u, v)$ and $(v, u)$ in the residual graph when $(u, v)$ is a forward edge on the augmenting path $P$. Show that is it also preserved for the edges $(u, v)$ and $(v, u)$ in the residual graph when $(u, v)$ is a backward edge in $P$.
Problem : Suppose that to build a single electric car we need a three-person team consisting of a machinist, a welder, and an electrician. We have a pool of $k$ machinists, $m$ welders, and $n$ electricians. Each tradesperson can be assigned to at most one team. Some pairs of machinists and welders refuse to work together, and some pairs of welders and electricians refuse to work together (the machinists and electricians do not work on the cars at the same time, so their personal squabbles are irrelevant). Describe a polynomial-time algorithm to determine the maximum number of teams we can form given the constraints on who will work with whom and prove that it is correct (hint: if you can solve the problem by creating an appropriate input to a standard algorithm then you need only explain why your input correctly models the problem).
Problem : Show that $3-SAT \le_P VERTEX\_COVER$ by showing how to, given a 3-CNF formula $\phi$, construct a graph $G$ and pick an integer $k$ so that $\phi$ has a satisfying assignment if and only if $G$ has a vertex cover of size at most $k$. (For your own benefit, prove that your $G$ and $k$ have that property.)
Problem : UNDIRECTED-HAMILTONIAN-PATH is NP-complete. But perhaps the problem becomes easier if we give ourselves a little wiggle room. Consider UNDIRECTED-APPROX-HP, which is the problem of, given an undirected, connected graph $G$, determining if $G$ has a path that visits $n-1$ vertices exactly once and the other vertex at least once, but traverses no edge more than once. Prove that this modified problem is not in fact any easier: UNDIRECTED-APPROX-HP is NP-complete (here we do want the proof that whatever construction you come up with does in fact work).