Question 12: Consider the following definitions: A vertex cover is a …

Consider the following definitions:

• A vertex cover is a subset $S$ of $V(G)$ such that for all $(u,v) \in E(G)$, $S \cap \{u,v\} \neq \emptyset$.
• An independent set is a subset $S$ of $V(G)$ such that for all $(u,v) \in S$, $\{u,v\} \notin E(G)$.
• A maximum matching in $G$ is a largest collection of edges $F \subseteq E(G)$ such that no two edges in $F$ have a common endpoint.
• A feedback vertex set is a subset $S$ of $V(G)$ such that $G \setminus S$ is acyclic.
• An odd cycle transversal is a subset $S$ of $V(G)$ such that $G \setminus S$ is bipartite.

Which of the following is not a valid lower bound for the size of a minimum vertex cover of a graph $G$?