Chapter 61. Vertex Covers

A vertex cover is a set of vertices that touches every edge of a graph. Vertex covers are fundamental objects in graph theory, combinatorial optimization, and theoretical computer science. They are closely connected to matchings, independent sets, network design, approximation algorithms, and computational complexity. (en.wikipedia.org)

The basic idea is simple. Instead of selecting edges, one selects vertices so that every edge is incident with at least one selected vertex. In many applications, the selected vertices represent monitoring stations, guards, servers, or control points.

Vertex covers form one of the classical covering problems in graph theory.

61.1 Definition

Let

G=(V,E)

be a graph.

A subset

C \subseteq V

is called a vertex cover if every edge of $G$ has at least one endpoint in $C$ .

Equivalently,

\forall uv \in E, \quad u \in C \quad \text{or} \quad v \in C.

Thus every edge is “covered” by at least one selected vertex.

For example, consider the path

v_1-v_2-v_3-v_4.

The set

C=\{v_2,v_3\}

is a vertex cover, because every edge touches either $v_2$ or $v_3$ .

The set

\{v_2\}

is not a vertex cover, because the edge

v_3v_4

is uncovered.

61.2 Minimum Vertex Covers

A vertex cover is minimum if it has smallest possible size.

The size of a minimum vertex cover is denoted by

\tau(G).

Thus,

\tau(G) = \min\{|C| : C \text{ is a vertex cover of } G\}.

The minimum vertex cover problem asks for a vertex cover of minimum size.

This optimization problem is central in algorithmic graph theory.

61.3 Trivial Vertex Covers

Some vertex covers are immediate.

Entire Vertex Set

The set

V

itself is always a vertex cover, because every edge has endpoints in $V$ .

Thus every graph has at least one vertex cover.

Empty Set

The empty set is a vertex cover only when the graph has no edges.

Indeed, if an edge exists, some vertex must cover it.

61.4 Vertex Covers in Standard Graphs

The minimum vertex cover size can often be computed explicitly for common graph families.

Paths

For the path graph $P_n$ ,

\tau(P_n) = \left\lfloor \frac{n}{2} \right\rfloor.

One may select every second vertex.

Cycles

For the cycle graph $C_n$ ,

\tau(C_n) = \left\lceil \frac{n}{2} \right\rceil.

Even cycles allow alternating selections. Odd cycles require one additional vertex.

Complete Graphs

For the complete graph $K_n$ ,

\tau(K_n)=n-1.

Indeed, if two vertices remain outside the cover, the edge joining them is uncovered.

Complete Bipartite Graphs

For

K_{m,n},

\tau(K_{m,n}) = \min(m,n).

Choosing all vertices from the smaller side covers every edge.

61.5 Relationship with Independent Sets

A set

I \subseteq V

is independent if no two vertices in $I$ are adjacent.

Vertex covers and independent sets are complementary concepts.

Theorem 61.1

A set

C \subseteq V

is a vertex cover if and only if

V \setminus C

is an independent set.

Proof

Suppose $C$ is a vertex cover.

If two vertices outside $C$ were adjacent, then the edge joining them would have neither endpoint in $C$ , contradicting the cover property.

Thus

V \setminus C

is independent.

Conversely, suppose

V \setminus C

is independent.

Then no edge has both endpoints outside $C$ . Therefore every edge has at least one endpoint in $C$ , so $C$ is a vertex cover.

This proves the equivalence.

61.6 Independence Number

Let

\alpha(G)

denote the size of a maximum independent set.

Since complements of vertex covers are independent sets:

\alpha(G)+\tau(G)=|V|.

\alpha(G)+\tau(G)=|V|

This identity is one of the most important relations in graph theory.

It converts covering problems into independence problems and vice versa.

61.7 Vertex Covers and Matchings

Vertex covers are closely connected to matchings.

Suppose $M$ is a matching and $C$ a vertex cover.

Every edge of $M$ must be covered by at least one vertex of $C$ .

Since the edges of $M$ are disjoint, distinct edges require distinct covering vertices.

Therefore,

|M| \le |C|.

Thus:

Every matching gives a lower bound on every vertex cover.

Taking maxima and minima yields:

\nu(G) \le \tau(G),

where

\nu(G)

is the maximum matching size.

61.8 König’s Theorem

For bipartite graphs, the previous inequality becomes equality.

Theorem 61.2. König’s Theorem.
If $G$ is bipartite, then

\nu(G)=\tau(G).

(en.wikipedia.org)

This theorem is one of the central min-max results in combinatorics.

It states:

Quantity	Meaning
Maximum matching	Largest packing of disjoint edges
Minimum vertex cover	Smallest covering of all edges

In bipartite graphs, these quantities coincide exactly.

61.9 Proof Idea of König’s Theorem

Let

M

be a maximum matching in a bipartite graph

G=(X \cup Y,E).

Build alternating trees from unmatched vertices of $X$ .

Define:

Set	Meaning
$Z_X$	Reachable vertices in $X$
$Z_Y$	Reachable vertices in $Y$

Then define:

C=(X \setminus Z_X)\cup Z_Y.

One proves:

$C$ is a vertex cover.
$|C|=|M|$ .

Since every vertex cover has size at least $|M|$ , equality follows.

61.10 Minimal and Minimum Vertex Covers

The terms minimal and minimum have different meanings.

Term	Meaning
Minimal	No vertex can be removed
Minimum	Smallest possible size

Every minimum vertex cover is minimal.

The converse is false.

Example

Consider the path

v_1-v_2-v_3-v_4.

The set

\{v_2,v_3\}

is minimal.

Removing either vertex leaves an uncovered edge.

However, the set

\{v_2,v_4\}

is smaller and also covers every edge.

Thus a minimal cover need not be minimum.

61.11 Vertex Cover Algorithms

Brute Force

One may test all subsets of vertices.

This requires:

2^{|V|}

possibilities.

Such exhaustive search becomes infeasible for large graphs.

Greedy Methods

Greedy algorithms repeatedly select vertices covering many uncovered edges.

These algorithms are fast but do not always produce minimum covers.

Exact Algorithms

More advanced algorithms use:

Technique	Purpose
Branch and bound	Reduce search space
Dynamic programming	Structured graphs
Integer programming	Optimization
Kernelization	Parameterized complexity

61.12 Complexity

The minimum vertex cover problem is NP-complete. (en.wikipedia.org)

Thus no polynomial-time algorithm is known for arbitrary graphs.

However:

Graph Type	Complexity
Bipartite graphs	Polynomial
Trees	Polynomial
General graphs	NP-complete

The bipartite case becomes tractable because of König’s theorem and flow techniques.

61.13 Approximation Algorithms

Although exact solutions may be difficult, good approximations exist.

A simple $2$ -approximation algorithm:

Choose any uncovered edge.
Add both endpoints to the cover.
Remove all covered edges.
Repeat.

This algorithm always produces a cover of size at most twice optimal.

Why It Works

The chosen edges form a matching.

Every vertex cover must contain at least one endpoint of each matching edge.

If the algorithm chooses $k$ edges, the optimal cover has size at least $k$ , while the algorithm outputs size $2k$ .

Hence:

|C| \le 2\tau(G).

61.14 Vertex Cover on Trees

For trees, minimum vertex covers can be found efficiently using dynamic programming.

At each vertex, consider two possibilities:

State	Meaning
Vertex included	Children optional
Vertex excluded	Children required

Combining subtree solutions yields a polynomial-time algorithm.

Trees avoid cycles, which greatly simplifies the optimization structure.

61.15 Edge Cover Duality

An edge cover is a set of edges touching every vertex.

Vertex covers and edge covers solve different covering problems:

Object Covered	Chosen Objects
Edges	Vertices
Vertices	Edges

The two notions are related indirectly through matching theory.

61.16 Hypergraph Vertex Covers

Vertex covers generalize naturally to hypergraphs.

A hypergraph edge may contain many vertices.

A vertex cover becomes a set intersecting every hyperedge.

This generalization appears in database theory, combinatorial optimization, and constraint systems.

61.17 Weighted Vertex Covers

In weighted versions, each vertex has cost:

w(v).

The objective becomes minimizing:

\sum_{v \in C} w(v).

Weighted vertex cover problems arise in network monitoring, sensor placement, and infrastructure planning.

Approximation algorithms and linear programming relaxations are especially important here.

61.18 Linear Programming Formulation

Introduce variables:

x_v= \begin{cases} 1, & v \in C, \\ 0, & v \notin C. \end{cases}

The optimization problem becomes:

\min \sum_{v \in V} x_v

subject to:

x_u+x_v \ge 1

for every edge

uv \in E.

x_u+x_v \ge 1

These inequalities enforce edge coverage.

The linear relaxation is central in approximation theory.

61.19 Applications

Vertex covers appear in many practical settings.

Application	Interpretation
Network monitoring	Monitor all communication links
Security systems	Place guards covering all corridors
Scheduling	Resolve pairwise conflicts
Computational biology	Cover interaction networks
Compiler optimization	Register allocation
Database systems	Constraint management

The abstraction is simple but widely applicable.

61.20 Common Relationships

Parameter	Relation
Matching number	$\nu(G)\le\tau(G)$
Independent number	(\alpha(G)+\tau(G)=
Bipartite graphs	$\nu(G)=\tau(G)$

These identities connect packing, covering, and independence.

61.21 Exercises

Find a minimum vertex cover of $P_6$ .
Compute $\tau(C_7)$ .
Prove that $V \setminus C$ is independent whenever $C$ is a vertex cover.
Show that every matching gives a lower bound on vertex cover size.
Find a minimum vertex cover of $K_{3,5}$ .
Prove that every minimum vertex cover is minimal.
Give an example of a minimal vertex cover that is not minimum.
Prove:

\alpha(G)+\tau(G)=|V|.

Apply the $2$ -approximation algorithm to a small graph.
Explain why vertex cover is easier on bipartite graphs than on arbitrary graphs.