It would seem weird that I am interested in a lower bound, rather than an upper bound, on the size of a minimal vertex cover of any simple graph $G$. However, since I reduce problems to SAT in practice, such lower bounds help the equivalent CNF formula.
Are there any known lower bounds on the size of the minimal vertex cover in any simple graph $G$?
There's a well known (see e.g. Vazirani's book, or Wikipedia) matching-based lower bound: the endpoints of all edges in a maximal matching form a vertex cover, so a vertex cover must contain at least one endpoint from each such edge.