# Minimum vertex cover and odd cycles

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.