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$?

  • $\begingroup$ Perhaps you can give some graph properties or parameters you might be interested in. As it stands, I can only see the trivial bound of the number of edges divided by the maximum degree. $\endgroup$ Jun 30, 2018 at 23:21
  • $\begingroup$ My only constraint is that the lower bound can be polynomial calculated $\endgroup$
    – TheNotMe
    Jul 1, 2018 at 7:55

1 Answer 1


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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .