- I fixed some small typos on the hw, please download the new version
- Problem 3:Hint: you only need to use the max-flow/min-cut theorem here. There is no need to use induction.
- Problem 4: Hint: Set this up as a min-cut problem. Classifying each vertex as foreground or background is equivalent to the vertex being on the s side or t side of the cut (in some new graph G')