Statement I: Given a graph G = (V, E) in which each vertex v ∈ V has an associated positive weight w(v), we can use linear programming to find a lower bound on the weight of the minimum-weight vertex cover.
Statement II: The lower bound can be found by maximising Σ_v∈V w(v)x(v) subject to x(u) + x(v) ≥ 1 for each (u, v) ∈ V, x(v) ≤ 1 and x(v) ≥ 0 for each v ∈ V.
Choose the most appropriate answer.

1. ABoth Statement I and Statement II are correct
2. BBoth Statement I and Statement II are incorrect
3. CStatement I is correct but Statement II is incorrect
4. DStatement I is incorrect but Statement II is correct

Pick an option to check yourself, or open the answer below.