  The vertex-cover problem is studied for random graphs $G_{N,cN}$ having $N$
vertices and $cN$ edges. Exact numerical results are obtained by a
branch-and-bound algorithm. It is found that a transition in the coverability
at a $c$-dependent threshold $x=x_c(c)$ appears, where $xN$ is the cardinality
of the vertex cover. This transition coincides with a sharp peak of the typical
numerical effort, which is needed to decide whether there exists a cover with
$xN$ vertices or not. For small edge concentrations $c\ll 0.5$, a cluster
expansion is performed, giving very accurate results in this regime. These
results are extended using methods developed in statistical physics. The so
called annealed approximation reproduces a rigorous bound on $x_c(c)$ which was
known previously. The main part of the paper contains an application of the
replica method. Within the replica symmetric ansatz the threshold $x_c(c)$ and
the critical backbone size $b_c(c)$ can be calculated. For $c<e/2$ the results
show an excellent agreement with the numerical findings. At average vertex
degree $2c=e$, an instability of the simple replica symmetric solution occurs.
