Vertex cover
= Vertex cover
{wiki}
A vertex cover is a set of <vertices> meeting every <edge> of a <graph>. The endpoints of any <maximal matching> form a vertex cover: an <edge> avoiding all endpoints would enlarge that <matching in a graph>. Consequently a <graph> with no <matching in a graph> of size $s$ has a vertex cover of size at most $2(s-1)$.