 Solution

For a finite undirected graph $G=(V,E)$, a vertex cover is a subset $C\subseteq V$ meeting every edge: for every $\{u,v\}\in E$, at least one of $u,v$ belongs to $C$. The optimization problem asks for a vertex cover of minimum cardinality. Its usual decision version also supplies an integer $k$ and asks whether one exists with $|C|\le k$.