Vertex Covers in Bipartite Graphs

Vertex Covers and Their Purpose

A vertex cover records a set of vertices that meets every edge. It gives a compact way to describe how the edges of a graph are collectively incident to vertices. In a bipartite graph, the two parts each provide an immediate cover, but a smaller cover may use vertices from both parts. To check any proposed cover, inspect every edge and confirm that at least one of its endpoints belongs to the set.

Throughout, graphs are finite, simple and undirected. A graph is bipartite if its vertex set can be partitioned into two parts $X$ and $Y$ so that every edge has one endpoint in each part. Either part may be empty. The notation $G=(V,E)$ gives the vertex set and edge set; an edge with endpoints $u$ and $v$ is written $uv$.

Definition: A vertex cover of $G=(V,E)$ is a set $C\subseteq V$ such that for every edge $uv\in E$, at least one of $u$ and $v$ belongs to $C$. The vertex cover number, denoted $\tau(G)$, is the smallest size of a vertex cover: $$ \tau(G)=\min\{|C|:C\subseteq V\text{ and }C\text{ is a vertex cover}\}. $$

The whole vertex set $V$ is always a cover, so a cover exists for every finite graph and the minimum in the definition is attained. If $E=\varnothing$, the empty set is a cover: there are no edges that it fails to meet. Thus $\tau(G)=0$ for an edgeless graph, including a graph with isolated vertices. An isolated vertex is a vertex incident to no edge, so it is never needed in a smallest cover.

Two different uses of the word “smallest” need to be kept separate. A minimum cover has the least possible cardinality. A cover is inclusion-minimal if none of its proper subsets is also a cover. Every minimum cover is inclusion-minimal, since a proper subset would be smaller. The reverse need not hold: an inclusion-minimal cover can have more vertices than another cover.

How to Check a Proposed Cover

For a finite graph, the definition gives a direct verification procedure: list the edges and check each one. A vertex belonging to the cover can account for several edges, but no edge may be skipped. If even one edge has both endpoints outside the proposed set, that set is not a cover.

In a bipartite graph with parts $X$ and $Y$, both $X$ and $Y$ are covers. Every edge has an endpoint in $X$, and it also has an endpoint in $Y$. Consequently, a cover of size at most $\min(|X|,|Y|)$ is always available. This is an upper bound, not generally an answer for the cover number: combining vertices from the two parts can sometimes do better than choosing an entire part.

Worked Example: A Cover of a Four-Vertex Path

Let $G=(V,E)$ be the simple graph with $V=\{a,b,c,d\}$ and $E=\{ab,bc,cd\}$. It is bipartite with parts $X=\{a,c\}$ and $Y=\{b,d\}$. We will find its cover number.

The set $C=\{b,c\}$ is a cover. Check all three edges: $ab$ has endpoint $b\in C$; $bc$ has both endpoints in $C$; and $cd$ has endpoint $c\in C$. Therefore $\tau(G)\le 2$.

To show that one vertex cannot suffice, test each possible singleton. The set $\{a\}$ misses edge $cd$; $\{b\}$ misses $cd$; $\{c\}$ misses $ab$; and $\{d\}$ misses $ab$. The empty set also misses every edge, since $E\ne\varnothing$. Thus every cover has at least two vertices, so $\tau(G)=2$.

Check: the proposed set has size $2$, and the lower-bound check rules out every set of smaller size. Substituting $C=\{b,c\}$ into the definition, each of $ab,bc,cd$ has an endpoint in $C$, as required.

Inclusion-Minimal Covers and Private Edges

A useful way to test whether a cover is inclusion-minimal is to ask whether each of its vertices is doing necessary work. If removing a vertex leaves a cover, that vertex was unnecessary. The following criterion makes this check precise.

Theorem: A vertex cover $C$ of a finite simple graph $G$ is inclusion-minimal if and only if every vertex $v\in C$ has an incident edge $vw$ with $w\notin C$. Such an edge is called a private edge for $v$ relative to $C$.

Proof. First suppose every $v\in C$ has a private edge $vw$ with $w\notin C$. Remove any one vertex $v$ from $C$. The edge $vw$ then has neither endpoint in $C\setminus\{v\}$, so $C\setminus\{v\}$ is not a cover. Any proper subset of $C$ omits at least one vertex $v$; it is contained in $C\setminus\{v\}$, and therefore also fails to cover $vw$. Hence $C$ is inclusion-minimal.

Conversely, suppose some $v\in C$ has no private edge. Every edge incident to $v$ must then have its other endpoint in $C$. Removing $v$ leaves every such edge covered by its other endpoint, and leaves all edges not incident to $v$ unchanged. Thus $C\setminus\{v\}$ is still a cover, so $C$ is not inclusion-minimal. The two implications prove the criterion. If $C=\varnothing$, the condition on its vertices holds vacuously, and the empty set is inclusion-minimal because it has no proper subset. $\square$

The criterion concerns inclusion, not size. A private edge proves that a particular vertex cannot be deleted while keeping a cover, but it does not prove that no different cover elsewhere in the graph is smaller.

Worked Example: A Minimal Cover That Is Not Minimum

Let $G=(V,E)$ have $V=\{o,u,v,w\}$ and $E=\{ou,ov,ow\}$. This is a bipartite graph with parts $X=\{o\}$ and $Y=\{u,v,w\}$. Consider the two covers $C_1=\{o\}$ and $C_2=\{u,v,w\}$.

For $C_1$, the edge $ou$ has endpoint $o\in C_1$, as do $ov$ and $ow$. Hence $C_1$ is a cover of size $1$. The empty set is not a cover because, for example, it contains neither endpoint of $ou$. Thus $\tau(G)=1$, and $C_1$ is a minimum cover.

For $C_2$, the edge $ou$ is covered by $u$, $ov$ by $v$, and $ow$ by $w$. Each of $u,v,w$ has a private edge: respectively $ou,ov,ow$, whose other endpoint $o$ is outside $C_2$. By the theorem, $C_2$ is inclusion-minimal. But its size is $3$, whereas $C_1$ has size $1$, so $C_2$ is not a minimum cover.

Check: every edge is in the displayed edge set $\{ou,ov,ow\}$, and the checks above account for all three. The sizes are $|C_1|=1$ and $|C_2|=3$; the example shows why “inclusion-minimal” does not mean “minimum.”

Cover Number of a Complete Bipartite Graph

For a complete bipartite graph $K_{r,s}$, the vertex set is partitioned into parts $X$ and $Y$, with $|X|=r$ and $|Y|=s$, and every vertex of $X$ is adjacent to every vertex of $Y$. There are no edges within either part. When both parts are nonempty, avoiding even one vertex from each part leaves an uncovered edge between those two vertices. This observation gives an exact formula.

Theorem: For nonnegative integers $r$ and $s$, the vertex cover number of the complete bipartite graph $K_{r,s}$ is $$ \tau(K_{r,s})=\min(r,s). $$

Proof. If $r=0$ or $s=0$, then $K_{r,s}$ has no edges. Its empty set is a cover, so its cover number is $0=\min(r,s)$.

Now suppose $r>0$ and $s>0$. The set $X$ is a cover because every edge has an endpoint in $X$; likewise $Y$ is a cover. Choosing the smaller part gives a cover of size $\min(r,s)$, so $\tau(K_{r,s})\le\min(r,s)$.

For the reverse inequality, let $C$ be any cover. If $C$ does not contain all of $X$, choose $x\in X\setminus C$. If it also does not contain all of $Y$, choose $y\in Y\setminus C$. Completeness gives the edge $xy$, and neither endpoint belongs to $C$, contradicting that $C$ is a cover. Therefore $C$ contains all of $X$ or all of $Y$, so $|C|\ge r$ or $|C|\ge s$, respectively. In either case $|C|\ge\min(r,s)$. This holds for every cover, proving the reverse inequality and the formula. $\square$

Worked Example: A Complete Bipartite Graph with an Isolated Vertex

Let $G=(V,E)$ have $V=\{a,b,c,d,z\}$ and $E=\{ab,ad,cb,cd\}$. The graph is bipartite with parts $X=\{a,c,z\}$ and $Y=\{b,d\}$. The vertex $z$ is isolated. The four edges listed are all the pairs between $\{a,c\}$ and $\{b,d\}$, so the non-isolated part of the graph is $K_{2,2}$.

The set $C=\{b,d\}$ covers every edge: $ab$ and $cb$ meet $b$, while $ad$ and $cd$ meet $d$. The set $\{a,c\}$ also covers every edge: $ab$ and $ad$ meet $a$, while $cb$ and $cd$ meet $c$. The isolated vertex $z$ is in neither set and is not needed.

To find the minimum size, apply the complete bipartite result to the four vertices in $\{a,b,c,d\}$: their cover number is $\min(2,2)=2$. Adding the isolated vertex does not change the cover number, because no edge is incident to it. Hence $\tau(G)=2$.

Check: substituting the set $\{b,d\}$ into the edge list gives a covered endpoint for each of $ab,ad,cb,cd$. The formula gives $\min(2,2)=2$, matching the size of this cover and the proved lower bound.

Common Pitfall: Checking Only the Outer Edges

A frequent error is to check only the edges that look like the “ends” of a graph and overlook an edge between uncovered vertices. In the four-vertex path from the first example, one might claim that $\{a,d\}$ is a cover because $a$ meets $ab$ and $d$ meets $cd$. But the remaining edge $bc$ has neither endpoint in $\{a,d\}$. Therefore $\{a,d\}$ is not a cover.

The correction is to check the entire edge set, not just the edges at the ends. For $E=\{ab,bc,cd\}$, the set $\{b,c\}$ covers $ab$ through $b$, $bc$ through both endpoints, and $cd$ through $c$. A complete edge-by-edge check is part of verifying any proposed cover, whether or not the graph is bipartite.

Vertex covers are useful because they turn a condition on every edge into a choice of vertices. In small graphs, listing the edges and testing candidate sets can settle the question directly. The distinction between a verified cover, an inclusion-minimal cover, and a minimum cover matters: the first meets every edge, the second cannot lose a vertex, and the third has the least possible size.

Check Your Understanding

For each question, use the stated edge set and check every edge relevant to your answer.

Let $V=\{p,q,r,s\}$ and $E=\{pq,qr,rs\}$. Is $\{q,r\}$ a vertex cover? Is it minimum? Justify both answers.
In a graph with no edges and four vertices, what is the vertex cover number? Explain why isolated vertices do not change it.
For $K_{3,5}$, give a cover of size $3$ and use the complete bipartite result to justify its minimum size.
In the graph $V=\{o,u,v\}$, $E=\{ou,ov\}$, decide whether $\{u,v\}$ is inclusion-minimal and whether it is minimum.
Give a concrete reason why checking only some of the edges cannot establish that a set is a vertex cover.