Suppose we have a graph $ G$ . Consider the minimum vertex cover problem of $ G$ formulated as a linear programming problem, that is for each vertex $ v_{i}$ we have the variable $ x_{i}$ , for each edge $ v_{i}v_{j}$ we have the constraint $ x_{i}+x_{j}\geq 1$ , for each variable we have $ 0\leq x_{i}\leq 1$ and we have the objective function $ \min \sum\limits_{1}^{n}{x_{i}}$ . We say such a linear programming problem *LP*. Note that it is NOT an integer linear programming problem.

We find a half integral optimal solution of *LP* that we say $ S_{hi}$ . For each variable $ x_{i}$ that takes value *0* in $ S_{hi}$ , we add the constraint $ x_{i}=0$ to *LP*.

For each odd cycle of $ G$ , add to *LP* the constraint $ x_{a}+x_{b}+x_{c}+…+x_{i}\geq \frac{1}{2}(k+1)$ where $ x_{a},x_{b},x_{c},…,x_{i}$ are the vertices of the cycle and $ k$ is the number of vertices of the cycle. We find a new optimal solution of *LP* that we say $ S$ .

If $ x_{i}$ is a variable that takes value $ 0.5$ in $ S_{hi}$ and value $ \gt 0.5$ in $ S$ , can we say that there is at least a minimum vertex cover of $ G$ that contains the vertex associated to $ x_{i}$ ?

The idea behind the question: in an odd cycle $ c$ with $ k$ vertices, the number of vertices needed to cover the cycle is $ \frac{1}{2}(k+1)$ , therefore for each odd cycle we add to *LP* the constraint $ x_{a}+x_{b}+x_{c}+…+x_{i}\geq \frac{1}{2}(k+1)$ . If in $ S_{hi}$ the sum of the variables of $ c$ is $ \frac{k}{2}$ (that is all the variables of $ c$ take value $ \frac{1}{2}$ ), then in $ S$ at least a variable $ x_{i}$ of $ c$ takes vale $ \gt \frac{1}{2}$ and the vertex associated to $ x_{i}$ belongs to at least a minimum vertex cover of the given graph.