Statement 1:
Given a graph $\mathrm{G}=(\mathrm{V}, \mathrm{E})$ in which each vertex $\mathrm{v} \in \mathrm{V}$ has an associated positive weight w(v), we can use linear programming to find the lower bound on the weight of the minimum-weight vertex cover.
Statement 2:
The lower bound can be found by maximizing the following
$\sum_{v \in V}^{n} \mathrm{w}(v) \mathrm{x}(v)$
$\text { subject to }$
$x(u)+x(v) \geq 1 \text { for each }(u, v) \in V$
$\quad x(v) \leq 1 \text { for each } v \in V$
$\quad x(v) \geq 0 \text { for each } v \in V$
In the light of the above statements, choose the most appropriate answer from the options given below:
- Both statement $\text{I}$ and Statement $\text{II}$ are correct
- Both statement $\text{I}$ and Statement $\text{II}$ are incorrect
- Statement $\mathrm{I}$ is correct but Statement $\text{II}$ is incorrect
- Statement $\text{I}$ is incorrect and Statement $\text{II}$ is correct
(Option $1 [39653]) 1$
(Option $2 [39654]) 2$
(Option $3 [39655]) 3$
(Option $4 [39656]) 4$
Answer Given by Candidate: $1$
