# Graph theory: for a connected graph, show that the size of the minimum vertex cover τ(G) is at most [(|E(G)| + 1)]/2

I'm having real trouble with this practice question:

Show that

$$\tau(G) ≤ \frac{|E(G)| + 1}{2}$$ for every connected graph G.

What properties of a connected graph entail this inequality? Does it tell us something about the number of vertices?

So if a graph is connected, every vertex has at least an edge incident to it. So $|V(G)|$ is at most $|E(G)|+1$, because the connected graph with smallest $|E(G)|$ is a tree with two leaves and all other vertices of degree 2. Is it that you only need half the vertices because an edge connects two vertices, and so since we have an upper bound for $|V(G)|$ we have an upper bound for $\tau(G)$? Am I going in the right direction?

Can anyone help? Thanks!

-

See theorem 2.4.17 in http://www.math.uiuc.edu/~kostochk/math581/Chapter2-4.pdf for a possible proof.

-

Your argument is fine, but will not give the result. I am afraid induction is needed.

(edit3) To adress the comments I will be more precise and explicit. Thanks. I formulate my observations avoiding $1\over 2$ as I am afraid of rounding errors.

Connected graph $G$ either is a tree, or is circular (i.e., it consists of a single cycle), or it contains a cycle with a vertex $v$ of degree at least three.

(i) In case $G$ is a tree alternatingly colour the vertices red and green. Pick the colour that occurs at most half the number of times as vertex-cover. If $G$ has $2t$ (resp. $2t-1$) edges and $2t+1$ (resp. $2t$) vertices we can pick $t$ vertices (both even and odd case), matching the bound in the question.

(ii) In case $G$ is a circle graph having $2t$ (resp. $2t-1$) edges and $2t$ (resp. $2t-1$) vertices we can pick $t$ vertices, again matching the bound.

(iii) Otherwise we can find a vertex $v$ on a cycle and with degree $k\ge 3$. Deleting $v$ and its incident edges will lead to a graph with $\ell$ components with $\ell < k$ (because of the cycle). Apply induction: for component $G_i$ we have $2\tau(G_i)\le |E_i|+1$. Choose $v$ in the vertex-cover and the other vertices inductively. $2\tau(G) \le 2 + 2\tau(G_1) +\dots+ 2\tau(G_\ell) \le 2 + |E_1| + \dots + |E_\ell| + \ell$. The total number of edges sums to $|E|-k$, while $\ell -k \le -1$, so we obtain $2+|E|-k + \ell \le |E| +1$.

That works, thanks again for the input.

-
Does it? How would you finish it? How does an edge connecting vertices imply that we only need half of them? – joriki Nov 5 '12 at 5:16
This still doesn't seem sufficient. This proves $$\tau \le \frac{|E|+2}{2}$$ – EuYu Nov 6 '12 at 19:42
Your second argument is not very clear. – EuYu Nov 6 '12 at 20:26