  In this paper we show that the problem of identifying an edge $(i,j)$ in a
graph $G$ such that there exists an optimal vertex cover $S$ of $G$ containing
exactly one of the nodes $i$ and $j$ is NP-hard. Such an edge is called a weak
edge. We then develop a polynomial time approximation algorithm for the vertex
cover problem with performance guarantee $2-\frac{1}{1+\sigma}$, where $\sigma$
is an upper bound on a measure related to a weak edge of a graph. Further, we
discuss a new relaxation of the vertex cover problem which is used in our
approximation algorithm to obtain smaller values of $\sigma$. We also obtain
linear programming representations of the vertex cover problem for special
graphs. Our results provide new insights into the approximability of the vertex
cover problem - a long standing open problem.
