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!
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
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.
