Weighted Vertex Cover and Linear Programming I want to prove the statement described in this question.
The answer given is great, though the way I understand it, it only proves $x_i \in \{0, \frac12, 1\}$ or $x_i>1$.
I would like to show that $x_i\not>1$, but don't know how to go about it, and would appreciate help.
Thanks!
 A: On further thought, you can probably use a variant of the idea we discussed in the comments. The key is that the polytope you care about doesn't actually depend on the weight vector at all, only on the constraints. You may have seen the argument that, given a set of constraints, every BFS $x$ has a cost vector $w$ such that $x$ is the unique solution that minimizes $w\cdot x$ subject to your constraints. (This is Lemma 2.2 in my copy of Papadimitriou--Steiglitz.)
In particular, if we renumber variables so that $x_1, \ldots, x_t$ are the variables used in the basis, then putting $w_i = 0$ for $i = 1, \ldots, t$ and $w_i = 1$ otherwise forces every optimal solution to have $x_j = 0$ for $j \notin 1, \ldots, t$, and therefore forces every optimal solution to be the BFS corresponding to $1, \ldots, t$.
Now if some $x_i > 1$ in our BFS, then reducing $x_i$ to $1$ would give another feasible solution with cost $0$ for the weight vector we constructed, contradicting the uniqueness of the solution.
