How to show that the Integrality Gap is $2$ for Minimum Vertex Cover problem?
Here is the ILP formulation : Assuming each vertex has cost $c(v) \geq 0$ : Minimize $\left(\displaystyle\sum_{v \in V(G)} c(v) \cdot x_v \right)$ subject to $\left(x_u + x_v \geq 1 \ \forall \ \{u,v\} \in E(G)\right) \land \left(x_v \in \{0,1\} \ \forall \ v \in V(G) \right)$.
One way to show is along the lines of Page 5 of this scribe. But if we don't know about the factor of $2$, how do we go on to prove that this is indeed so? I have a hunch that the particular constraint $x_u + x_v \geq 1$ provokes us to show that $x^{*}_u + x^{*}_v = \frac{1}{2} + \frac{1}{2} \geq 1$ gives an optimum solution. Is there a more intuitive way or a way that is applicable to the general case, especially when the optimum can not be guessed the way it can be here?
You are pretty close. I won't give a full proof, but a hint.
Consider an optimum $x^*$ of the LP. Now consider $S = \{v\in V | x^*_v \geq \frac{1}{2}\}$. Can you notice anything special about this set?
The hint for the factor 2 here, is the symmetry in the constraint $x_u + x_v \geq 1$.
Edit: Nevermind, just saw that the link you provided provides the exact proof you were after.
In general in integer programming, this 'rounding' to the closest integer solution is not an uncommon technique. In this particular case, the symmetry from the equation $x_u+x_v\geq 1$ is relevant. You could also consider the same problem for graphs for which any triplet $(u,v,w)$ of vertices forms a 3-clique, for example. Then, you would have $x_u+x_v+x_w\geq 1, \forall u,v,w\in E$. And you could apply similar arguments to get an integrality gap of 3.
I don't really understand why you say one needs to argue that $x^*_u = x^*_v = \frac{1}{2}$, the proof you linked does not do this. They simply assume a given optimum $x^*$ which satisfies the linear relaxation exists.