I am currently working on the following problem:
Let $\tau(G)$ be the minimum size of a vertex cover of a graph $G=(V,E)$. Show that for $|V|=n$, $|E|=m$, we have $$\tau(G)\leq\frac{2mn}{2m+n}$$
I am completely struggling with this. I know that we definitely have $\tau(G)\leq|V|-1$, however even trying for $G=C_4$, we already have $\tau(C_4)=8/3<3=|V(C_4)|-1$, so showing that $\tau(G)\leq n-1\leq2mn/(2m+n)$ is not possible.
As such, any help is greatly appreciated!
First of all note that $\tau(G) + \alpha(G)=n,$ where $\alpha(G)$ is the size of the largest independent set. The reason for this is that the complement of a vertex cover is an independent set, and vice versa, by the definitions of these two notions. Now, the Caro-Wei Theorem givens an lower bound for $\alpha(G),$ and therefore an upper bound for $\tau(G).$
Specifically, $$ \alpha(G) \ge \frac{n}{1+d}, $$ where $d$ is the average degree, which is equal to $\sum_{v\in V}\deg(v) / n.$ Thus $$ \tau(G) = n - \alpha(G) \le n - \frac{n}{1+2m/n} = \frac{2mn}{n+2m}. $$