Vertex cover in a graph with maximum degree of 3 and average degree of 2. 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
 A: 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$.
A: After some thoughts I think that I got the answer but if someone wants to check it, I'll be glad.
Let $G$ be a graph with $|E(G)|=|V(G)|$ of degree max $3$.
If there is no single edge in the graph, we have the result. (By single edge I mean an edge disconnected from the rest of $G$)
Let $R$ be an empty set of vertices. (This set will contain the vertices of a vertex cover of $G$ of size at most $\frac{2}{3} E(G)$.)
Assume that there is a single edge (x,y) in $G$.
Add $x$ to $R$. 
As the average degree is $2$, for every  vertex of degree $1$ there is one of degree $3$.
Add any vertex z of degree $3$ to $R$.
Now consider $G'=G\setminus \{x,y,z\}$.
$|V(G')|$ = $|V(G)|-3$
$|E(G')|$ = $|E(G)|-4$
Add an edge to $G'$ in a way such that its maximal degree is still $3$. Clearly this is possible and does not decrease the size of its minimal vertex cover.
If $G'$ does not contain a single edge, let R' be a minimal vertex cover  of $G'$ and let $R=R\cup R'$. 
$R$ is a vertex cover of $G$ of size at most $\frac{2}{3} E(G)$, we have the result.
Otherwise, repeat the previous steps on G'.
