In the k-Flow problem, you are given a graph G = (V, E), an integer k, a source s V , and a sink t V . You are wondering if there is a flow from s to t of value k.

(a) Your fellow student shows you his proof, and it is a (correct) reduction from k-Flow to 3-SAT for NP completeness. What are the implications of this proof?

(b) The student modifies his reduction in the following manner: Given a 3-SAT instance, create the following k-Flow instance: For each literal xi , create two nodes labeled xi and xi . For each clause cj , create a node cj . Create two more nodes s and t. Connect s to every xi and xi with an edge of infinite capacity. Add an edge of capacity 1 from every cj to t. For each clause cj , add an edge of capacity 1 from each literal in cj to the node cj .

The 3-SAT instance is satisfiable iff there is a flow from s to t equal to the number of clauses. Is this a correct proof that k-Flow is NP-Complete? Explain your answer