# Bound on the largest minimal vertex cover in a graph

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 \frac{n-1}{3}$? If so, can you point out any reference? If not, what is an easy counterexample? Thanks!

Note: In the old version of the question I was asking whether the maximum cardinality of a minimal vertex cover of $G$ is $\geq \lfloor \frac{n}{2} \rfloor$. This is not true in general (consider, for example, a triangle with three whiskers attached to each of its vertices).

Let $\alpha(G)$ and $i(G)$ be the maximum cardinality of a minimal vertex cover of $G$ and the minimum cardinality of a maximal independent set of a graph $G = (V, E)$, respectively. It is known that $$\alpha(G) + i(G) = |V| = n \tag{\spadesuit} \label{eq:1}$$
Motivated by your example, consider a clique $C_k$ of size $k > 1$. For each vertex $v$ of $C_k$, create $k$ new vertices and connect each of them to $v$. In the new graph $G$ obtained, if a maximal independent set contains no vertex of $C_k$, it has size $k^2$; otherwise, it has size $(k - 1)k + 1$. Therefore, $$i(G) = (k - 1)k + 1$$ and $$\alpha(G) = |V| - i(G) = k(k + 1) - i(G) = 2k - 1$$ By letting $k = 5$, we have $\alpha(G) = 9$ and $n = |V| = 30$, where $$\alpha(G) < \frac{n-1}{3}$$