Minimum vertex cover algorithm with linear programming

Question

Consider the following algorithm: given a graph $G$ with $n$ vertices, set up a linear programming problem LP where there is a variable $x_i$ for each vertex $v_i$ of $G$, each variable can take value $\geq 0$, for each edge $v_av_b$ of $G$ set the constraint $x_a+x_b\geq 1$. The objective function is $\min\sum\limits_{1}^{n}{x_i}$. Find the variable (or one of the variables) $x_i$, among the variables not set to $0$, that set to $0$ gives the minimum value of the objective function. Add the constraint $x_i=0$ to LP. Repeat until the optimal solution of LP is integer (that is each variable takes value in $\left\{0; 1\right\}$).

I am looking for a graph where the vertices associated to the variables that take value $1$ in the final optimal solution of LP are not a minimum vertex cover of $G$ (if it exists).

Answer 1

Consider the graph

  2-4---7
 /  |\ /|
1   | × |
 \  |/ \|
  3-5---6

Setting $x_1,x_2,x_3,x_6$ or $x_7$ to 0 gives your LP a value of 4, while setting $x_4$ or $x_5$ to 0 gives your LP a value of 5. However, if you set $x_1=0$, you will finally get a vertex cover of size 5, while the optimal vertex cover is of size 4.