Vertex cover

Definition

Let $G$ be a graph. A vertex cover of $G$ is a set $S$ of vertices of $G$ that contains at least one end of each edge.

Remarks

A set $S$ is a vertex cover if and only if its complement is an independent set. For the complete bipartite graph $K_{m,n}$, the least size of a vertex cover is $\min\{m, n\}$. Each vertex of a cover meets at most one edge of a matching. Thus every vertex cover has at least as many vertices as any matching has edges.

Explanations

L1 human

A vertex cover is a set of vertices that touches every edge. Think of guards at crossings: each street must have a guard at one of its two ends.