Mathwords logoMathwords

Minimum Vertex Cover — Definition, Formula & Examples

A minimum vertex cover is the smallest set of vertices in a graph such that every edge has at least one endpoint in that set. It represents the most efficient way to 'cover' all edges using vertices.

Given an undirected graph G=(V,E)G = (V, E), a vertex cover is a subset S⊆VS \subseteq V such that for every edge (u,v)∈E(u, v) \in E, at least one of uu or vv belongs to SS. A minimum vertex cover is a vertex cover of smallest cardinality among all vertex covers of GG.

How It Works

To find a minimum vertex cover, you need to select as few vertices as possible while ensuring every edge in the graph is incident to at least one selected vertex. For small graphs, you can check this by inspection or brute force. For general graphs, finding a minimum vertex cover is NP-hard, meaning no known polynomial-time algorithm solves it exactly for all inputs. However, a simple 2-approximation algorithm exists: repeatedly pick any uncovered edge, add both its endpoints to the cover, and remove all edges incident to those vertices. König's theorem provides an exact polynomial-time solution for bipartite graphs by equating the minimum vertex cover size to the maximum matching size.

Worked Example

Problem: Find a minimum vertex cover of the graph with vertices {A,B,C,D}\{A, B, C, D\} and edges {(A,B), (A,C), (B,D), (C,D)}\{(A,B),\,(A,C),\,(B,D),\,(C,D)\}.
Step 1: List all edges and note which vertices each edge requires. Edge (A,B)(A,B) needs AA or BB; edge (A,C)(A,C) needs AA or CC; edge (B,D)(B,D) needs BB or DD; edge (C,D)(C,D) needs CC or DD.
Step 2: Try a two-vertex cover. Choosing S={A,D}S = \{A, D\}: edge (A,B)(A,B) is covered by AA, edge (A,C)(A,C) is covered by AA, edge (B,D)(B,D) is covered by DD, edge (C,D)(C,D) is covered by DD. All four edges are covered.
S={A,D}S = \{A, D\}
Step 3: Verify no single vertex covers all edges. Vertex AA alone misses (B,D)(B,D), and vertex DD alone misses (A,B)(A,B) and (A,C)(A,C). So a cover of size 1 is impossible.
Answer: The minimum vertex cover is {A,D}\{A, D\} with size 2. (Note: {B,C}\{B, C\} is also a minimum vertex cover of the same size.)

Why It Matters

Minimum vertex cover appears in algorithm design courses when studying NP-completeness, since it is one of Karp's 21 NP-complete problems. It models real problems like placing the fewest security cameras to monitor every corridor or selecting the fewest sensors to cover every network link.

Common Mistakes

Mistake: Confusing minimum vertex cover with minimum edge cover or independent set.
Correction: A vertex cover selects vertices to cover all edges. An edge cover selects edges to cover all vertices. An independent set is actually the complement of a vertex cover: SS is a vertex cover of GG if and only if V∖SV \setminus S is an independent set.