= Vertex cover
{wiki}
A <vertex cover> chooses <vertices> that collectively touch every <edge> of a <graph>. Think of placing monitors at junctions: if a monitor watches every connection incident to its junction, a <vertex cover> watches all connections. The <minimum vertex cover> asks how few monitors suffice. This is a model of covering connections through their endpoints, rather than of monitoring distances in the drawing.
For a finite <simple graph> $G=(V,E)$, a <vertex cover> is a <subset> $C\subseteq V$ satisfying
$$
\{u,v\}\in E\Longrightarrow u\in C\ \text{or}\ v\in C.
$$
Both endpoints may be selected; the condition requires at least one. An <isolated vertex> covers no <edge>, so a <minimum vertex cover> never needs it.<Graph Theory by Reinhard Diestel>[Diestel, Graph Theory, fourth electronic edition, Section 2.1, definition of vertex cover]{ref}
Take the <cycle graph> $C_5$ with <vertices> $0,1,2,3,4$ and <edges> $01,12,23,34,40$. The <set> $C=\{1,3,4\}$ is a <vertex cover>: <vertex> $1$ covers $01$ and $12$, <vertex> $3$ covers $23$ and $34$, and <vertex> $4$ covers $40$ as well as $34$. In particular, the closing <edge> $40$ is covered even though <vertex> $0$ is unselected.
The unselected <vertices> $I=V\setminus C=\{0,2\}$ form an <independent set>. This is the key connection: an <edge> missed by $C$ would have both endpoints in $I$, precisely what an <independent set> forbids. For every <subset> $C\subseteq V$,
$$
C\text{ is a vertex cover}\quad\Longleftrightarrow\quad V\setminus C\text{ is an independent set}.
$$
Here $V\setminus C$ is the <complement of a set> within $V$; the <graph> itself keeps all its <edges>. The <complement graph> is a different construction.https://introtcs.org/public/lec_12_NP.html[Barak, Introduction to Theoretical Computer Science, Chapter 14, vertex-cover exercise]{ref}
\Image[/vertex-cover-independent-complement.png]
{title=A minimum vertex cover and its maximum independent complement on the same five-cycle}
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)$. This supplies a convenient <vertex cover>, but it need not be a <minimum vertex cover>.
Back to article page
