Su argumento es correcto, pero no dará el resultado. Me temo que se necesita inducción.
(edit3) Para abordar los comentarios seré más preciso y explícito. Gracias. Formulo mis observaciones evitando $1\over 2$ ya que temo errores de redondeo.
El grafo conectado $G$ es un árbol, o es circular (es decir, consta de un solo ciclo), o contiene un ciclo con un vértice $v$ de grado al menos tres.
(i) En caso de que $G$ sea un árbol, colorea alternativamente los vértices en rojo y verde. Elije el color que ocurra como máximo la mitad de veces que la cobertura de vértices. Si $G$ tiene $2t$ (o $2t-1$) aristas y $2t+1$ (o $2t$) vértices podemos elegir $t$ vértices (en ambos casos, par e impar), igualando el límite en la pregunta.
(ii) En caso de que $G$ sea un grafo circular con $2t$ (o $2t-1$) aristas y $2t$ (o $2t-1$) vértices podemos elegir $t$ vértices, nuevamente igualando el límite.
(iii) De lo contrario, podemos encontrar un vértice $v$ en un ciclo y con grado $k\ge 3$. Eliminar $v$ y sus aristas incidentes llevará a un grafo con $\ell$ componentes con $\ell < k$ (debido al ciclo). Aplicamos inducción: para la componente $G_i$ tenemos $2\tau(G_i) \le |E_i|+1$. Elegimos $v$ en la cobertura de vértices y los otros vértices de forma inductiva. $2\tau(G) \le 2 + 2\tau(G_1) +\dots+ 2\tau(G_\ell) \le 2 + |E_1| + \dots + |E_\ell| + \ell$. El número total de aristas se suma a $|E|-k$, mientras que $\ell -k \le -1$, por lo que obtenemos $2+|E|-k + \ell \le |E| +1.
Eso funciona, gracias de nuevo por la contribución.
