Let $G$ be a graph with the same number of vertices and edges and maximum degree of 3.
For reasons that I will explain, I believe that a minimum vertex cover has size at most $\frac{2}{3} |E(G)|$.
I might very well be wrong and if you have a counter example, that will solve it!
Note that G is not necessarly connected, otherwise we have $\tau (G) \leq \frac{1}{2} (|E(G)|+1)$ and this solves the problem.
My intuition comes from the following observations:
If all vertices are of degree $2$, then the worst case is if the graph is just a set of triangles, then we have exactly $\tau (G) = \frac{2}{3} |E(G)|$.
If there is no single edge in the graph, the results holds. (Any connected grah of size at least 4 has $\tau (G) \leq \frac{2}{3} |E(G)|$)
If there is a single edge, then we have two vertices of degree $1$ and also two vertices of degree $3$. Those two vertices of degree $3$ should help in maintaining the minimum vertex cover below a certain bound (this is the intuition part).
I tried to create some bad cases with graphs containing single edges. I believe that one of the worst case is if the graph has 2 single edges and a K4. Then $|E(G)|=|V(G)|=8$ and $\tau (G)= \frac{5}{8} |E(G)|$, the result still holds.
I never really worked on vertex cover, so I am probably missing some important results that would help solving this problem. Also my intuition on this area is probably kind of weak.
Thanks a lot
Best Answer
Any $n$-vertex graph with average degree at most $2$, no matter what the maximum degree is, has a vertex cover of size at most $\frac23n$. Also, if the average degree is exactly $2$, then the number of edges is also $n$, and this gives the bound you wanted.
To see this, start from the Caro-Wei theorem, which guarantees that in any graph $G$, there is an independent set of size at least $$ \sum_{v \in V(G)} \frac1{\deg(v) + 1}. $$ By convexity of $x \mapsto \frac1{x+1}$ (for nonnegative $x$) this is at least $\frac{n}{d+1}$, where $d$ is the average degree. (This statement is also a variant of Turán's theorem.)
If the average degree is at most $2$, then there is an independent set of size at least $\frac13n$, and its complement is a vertex cover of size at most $\frac23 n$.