vertex cover , linear program extreme point Consider the vertex cover problem.
How can I prove that any extreme point of the linear program
\begin{aligned}
\min & & \sum_{i \in V} w_i x_i \\
\text{s.t.} & & x_i + x_j &\ge  1 & &\forall\,(i,j) \in E\\
         & &  x_i  &\ge  0 & & \forall\, i \in V
\end{aligned}
has the property that $x_i \in \{0, \frac12, 1\}$ for all $i \in V$? (Recall that an extreme point $x$ is a feasible solution that cannot be expressed as $\lambda x^1 + (1-\lambda)x^2$ for $0<\lambda<1$ and feasible solutions $x^1$ and $x^2$ distinct from $x$.)
 A: Given any feasible solution $x$, define $V^+ \subseteq V = \{i \in V : \frac12 < x_i < 1\}$ and $V^- \subseteq V = \{i \in V : 0 < x_i < \frac12\}$. For any $\epsilon>0$, $x$ is the midpoint of $y$ and $z$ such that
$$y_i = \begin{cases}
   x_i + \epsilon & i \in V^+ \\
   x_i - \epsilon & i \in V^- \\
   x_i & \text{else,}
\end{cases}
\qquad
z_i = \begin{cases}
   x_i - \epsilon & i \in V^+ \\
   x_i + \epsilon & i \in V^- \\
   x_i & \text{else.}
\end{cases}
$$
I claim that for sufficiently small $\epsilon>0$, both $y$ and $z$ are feasible. Whenever one of the constraints in the LP is not tight for $x$, we just ask for $\epsilon$ to be less than half the slack, and then the constraint will still be satisfied for $y$ and $z$. When the $x_i \ge 0$ constraint is tight, we have $y_i = z_i = x_i = 0$, and the constraint is also still satisfied for $y$ and $z$. So we only need to worry about tight constraints of the form $x_i + x_j = 1$ for $(i,j) \in E$.
We can assume that one of $i$ or $j$ is in $V^+ \cup V^-$, because otherwise we just have $y_i + y_j = x_i + x_j = 1$ and $z_i + z_j = x_i + x_j = 1$. Without loss of generality, $i \in V^+$; then $x_j = 1 - x_i \in (0, \frac12)$ so $j \in V^-$. In this case, $y_i + y_j = (x_i + \epsilon) + (x_j - \epsilon) = 1$ and $z_i + z_j = (x_i -\epsilon) + (x_j +\epsilon) = 1$, so the constraints are still satisfied for $y$ and $z$.
But if $x = \frac{y+z}{2}$, then $x$ can only be an extreme point if $x=y=z$, which means that $V^+ = V^- = \varnothing$ and $x$ is half-integral.
(Source: these lecture notes.)
