Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
add comment

1 Answer 1

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.

share|improve this answer
3  
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
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.