Vertex Cover

Definition

Vertex Cover

Let $G=(V,E)$ be a finite undirected graph. A vertex cover is a subset $C\subseteq V$ that intersects every edge:

$$C\text{ is a vertex cover of }G⟺\forall \{u,v\}\in E:\{u,v\}\cap C\ne \varnothing .$$

Thus, every edge has at least one endpoint in $C$. A vertex cover need not be minimum; it only needs to cover all edges.

In the graph below, $C=\{v_2,v_4\}$ is a vertex cover. The orange vertices touch every edge.

Complement Characterisation

Vertex Cover–Independent Set Complement

Let $G=(V,E)$ be a graph, let $C\subseteq V$, and let $I=V\setminus C$. Then $C$ is a vertex cover if and only if $I$ is an independent set:

$$C\text{ is a vertex cover of }G⟺I\text{ is independent in }G.$$