Let $G$ be a (connected) graph with $n$ vertices. Is it true that the maximum cardinality of a minimal vertex cover of $G$ is $\geq \lfloor \frac{n}{2} \rfloor$? If so, can you point out any reference? If not, what is an easy counterexample? Thanks!


Take a complete graph $K_d$. For every its vertex $u$, take $d$ more vertices connected just to $u$. We get $d(d+1)$ vertices in total.

Every minimal vertex cover contains all but one vertices of $K_d$. Either it contain all of them (and then it contains just $d$ vertices), or it does not contain some $u$ --- then it should contain $d$ extra vertices connected just to $u$. Thus it contains at most $2d-1$ vertices, which is $\Theta(2\sqrt{d(d+1)}$.

Perhaps, this bound is tight? Surely, we need at least $O(\sqrt n)$ vertices. Indeed, assume that the cover contains $o(\sqrt n)$ vertices; the complement of the cover is an independent set of $n-o(\sqrt n)$ vertices, so it contains $O(\sqrt n)$ vertices connected to one vertex $v$ from the cover. Then any minimal subcover in $V\setminus\{v\}$ contains at least $O(\sqrt n)$ vertices.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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