I'm trying to investigate the results of running the follwing factor two algorithm for minimum vertex cover on random graphs:

https://en.wikipedia.org/wiki/Vertex_cover#Pseudo_Code
To be more specific, for a given number of vertices $n$ I'm trying to find the smallest $p$ so that running the approximation algorithm above on a random graph $G(n,p)$ will give me (with high probability) a vertex cover with a size that is less then 80% from $n$. For example, I run some tests in java with this algorithm implementation and found:

For a graph with 60 vertices- $p<9$% will give the desired results.

For a graph with 300 vertices - $p<0.7$% will give the desired results.

For a graph with 3500 vertices - $p<0.3$% will give the desired results.

As it can be seen, the larger the number of vertices - the smaller the number of $p$ needed for my desired results.

My try for explaining those results: since in a graph $G(V,E)$ we know that $|E| = O(V^2)$, if we enlarge $|V|$ then the number of possibilities for edges will be much greater relative to the enlargement of $|V|$. Therefore, if we have graphs $G(n,p), G'(n' , p)$ when $n'>n$ then it's more likely that $G'$ will contain more edges.

Let's denote by $c^*$ and $c'^*$ the minimal vertex cover of $G$ and $G'$, and by $c$ and $c'$ the approximated vertex cover of $G$ and $G'$. Since their edges were randomly selected and we have more edges in $G'$ - it's more likely that $c^*/n < c'^*/n$ and therefore also $c/n < c'/n$.

There are few things I'm not sure about

:

1. The last line of the explanation when I wrote that the fact that the edges where randomly selected help us deduce the desired results. Is my explanation correct?

2. It seems that my results are relating to a general vertex cover, and are not specific only for the approximated algorithm. Am I right here?