Independent Sets as Complements of Vertex Covers

Complementation Reverses the Two Conditions

Independent sets and vertex covers describe opposite ways to account for the edges of a graph. An independent set avoids taking both endpoints of any edge. A vertex cover takes at least one endpoint of every edge. Complementation turns one condition into the other: the vertices left out of a cover form an independent set, and the vertices left out of an independent set form a cover.

All graphs in this tutorial are finite and simple. For a set $S\subseteq V(G)$, its complement in the vertex set is $V(G)\setminus S$; this is not the complement graph $\overline{G}$. We use $\alpha(G)$ for the maximum size of an independent set and $\tau(G)$ for the minimum size of a vertex cover.

Definition: A set $I\subseteq V(G)$ is independent if no edge of $G$ has both endpoints in $I$. A set $C\subseteq V(G)$ is a vertex cover if every edge of $G$ has at least one endpoint in $C$. A maximum independent set has largest cardinality among independent sets; a minimum vertex cover has smallest cardinality among vertex covers.

These definitions include the graph with no vertices and the graph with vertices but no edges. In either case the empty set is independent and is a vertex cover, since there are no edges to violate either condition. For any finite graph, the largest and smallest cardinalities in the definitions exist because there are only finitely many vertex subsets.

The Complement Correspondence

Theorem: For every graph $G=(V,E)$ and every set $I\subseteq V$, $I$ is independent if and only if $V\setminus I$ is a vertex cover.

Proof. First suppose $I$ is independent. Take any edge $uv\in E$. Its endpoints cannot both belong to $I$, by independence. Thus at least one of $u,v$ is outside $I$, and so belongs to $V\setminus I$. This holds for every edge, proving that $V\setminus I$ is a vertex cover.

Conversely, suppose $V\setminus I$ is a vertex cover. If $I$ were not independent, there would be an edge $uv\in E$ with both $u\in I$ and $v\in I$. Neither endpoint would then belong to $V\setminus I$, so this edge would have no endpoint in the proposed cover. That contradicts the definition of vertex cover. Therefore $I$ is independent. The argument also applies when $V$ or $E$ is empty: in those cases the relevant edge condition is vacuous. $\square$

Equivalently, for every $C\subseteq V$, $C$ is a vertex cover if and only if $V\setminus C$ is independent. This follows by applying the theorem to $I=V\setminus C$, since $V\setminus(V\setminus C)=C$. Complementation is therefore a one-to-one correspondence between all independent sets and all vertex covers, not merely between the optimal ones.

What Happens to the Optimal Sizes

Corollary: For every finite graph $G$, $$ \alpha(G)+\tau(G)=|V(G)|. $$ The complement of every minimum vertex cover is a maximum independent set, and the complement of every maximum independent set is a minimum vertex cover.

Proof. Write $n=|V(G)|$. If $C$ is a minimum vertex cover, then $I=V(G)\setminus C$ is independent by the complement correspondence, and $|I|=n-|C|=n-\tau(G)$. To show that $I$ is maximum, suppose there were an independent set $J$ with $|J|>|I|$. Then $V(G)\setminus J$ would be a vertex cover with size $n-|J|<n-|I|=\tau(G)$, contradicting the minimality of $C$. Thus $|I|=\alpha(G)$, so $\alpha(G)+\tau(G)=n$.

For the other direction, let $I$ be a maximum independent set. Its complement is a vertex cover and has size $n-\alpha(G)$. If there were a vertex cover $D$ of smaller size, then $V(G)\setminus D$ would be independent and would have size $n-|D|>n-(n-\alpha(G))=\alpha(G)$, contradicting the maximal cardinality of $I$. Hence $V(G)\setminus I$ is a minimum vertex cover. This reasoning also covers $n=0$: both parameters are $0$, and the unique sets are empty. $\square$

The equality relates the two optimal sizes, but its set-level meaning needs care. Every minimum cover has a maximum independent set as its complement, and every maximum independent set has a minimum cover as its complement. It does not follow that an independently chosen minimum cover and maximum independent set must be complements. There may be several optimal sets of either kind, and the correspondence pairs them by complementation.

Worked Example: A Path on Five Vertices

Let $G=(V,E)$, where $V=\{1,2,3,4,5\}$ and $E=\{12,23,34,45\}$. We will find a maximum independent set using a minimum vertex cover.

Consider $C=\{2,4\}$. The edge $12$ has endpoint $2\in C$; $23$ has endpoint $2\in C$; $34$ has endpoint $4\in C$; and $45$ has endpoint $4\in C$. Thus $C$ is a cover of size $2$. The edges $12$ and $45$ have disjoint endpoint sets, so any cover must choose at least one vertex from $\{1,2\}$ and at least one from $\{4,5\}$. These requirements concern disjoint sets, so every cover has size at least $2$. Therefore $C$ is a minimum cover and $\tau(G)=2$.

Its complement is $V\setminus C=\{1,3,5\}$, of size $5-2=3$. The edges $12,23,34,45$ each have an endpoint outside this set, so no edge has both endpoints in $\{1,3,5\}$; it is independent. By the corollary, it is maximum and $\alpha(G)=3$.

Check: the identity gives $\alpha(G)=|V|-\tau(G)=5-2=3$, agreeing with the three vertices found. Also, a larger independent set would have at least four vertices and its complement would be a cover of size at most $5-4=1$, contradicting the lower bound of $2$ for covers.

Worked Example: A Complete Bipartite Graph

Let $G=(V,E)$ have $V=\{a_1,a_2,b_1,b_2,b_3\}$ and $E=\{a_1b_1,a_1b_2,a_1b_3,a_2b_1,a_2b_2,a_2b_3\}$. This is $K_{2,3}$; the edge set lists all six pairs between the two displayed groups.

The set $C=\{a_1,a_2\}$ covers every listed edge, because each edge has one of these two endpoints. It has size $2$. The edges $a_1b_1$ and $a_2b_2$ are disjoint, so any cover needs at least one endpoint from each of their disjoint endpoint pairs. Hence every cover has at least two vertices, and $\tau(G)=2$.

The complement is $\{b_1,b_2,b_3\}$. No edge has both endpoints there, since every edge joins an $a$-vertex to a $b$-vertex. This independent set has size $3$, and the corollary proves it is maximum: $\alpha(G)=5-2=3$.

Check: directly, an independent set containing $a_1$ cannot contain any $b_i$, because all three edges $a_1b_i$ are present; it can contain at most $a_2$ in addition. Thus an independent set containing an $a$-vertex has size at most $2$. An independent set containing no $a$-vertex is a subset of $\{b_1,b_2,b_3\}$, so has size at most $3$. The set of all three $b$-vertices attains that bound. The six edges are also accounted for by the explicit list, consistent with each of the two $a$-vertices having three neighbors.

Optimal Sets Need Not Pair Arbitrarily

Worked Example: An Isolated Vertex and Several Optimal Choices

Let $G=(V,E)$, where $V=\{a,b,c,z\}$ and $E=\{ab,bc,ca\}$. The vertices $a,b,c$ form a triangle, and $z$ is isolated.

A cover must contain at least two of $a,b,c$: if it contained at most one, the other two triangle vertices would form an edge with neither endpoint covered. The set $C=\{a,b\}$ covers $ab$ using both endpoints, $bc$ using $b$, and $ca$ using $a$. The isolated vertex $z$ is not needed to cover any edge. Therefore $C$ is a minimum cover and $\tau(G)=2$. Its complement is $V\setminus C=\{c,z\}$, which is independent and has size $4-2=2$.

For comparison, the maximum independent sets are $\{a,z\}$, $\{b,z\}$, and $\{c,z\}$. An independent set can contain at most one triangle vertex, because every pair of triangle vertices is adjacent; it can always include $z$. Thus the largest possible size is $2$, and $\alpha(G)=2$. The complements of these three sets are, respectively, $\{b,c\}$, $\{a,c\}$, and $\{a,b\}$, all minimum covers.

Check: the identity gives $2+2=4=|V|$. In particular, the chosen minimum cover $\{a,b\}$ and the maximum independent set $\{a,z\}$ are not complements: they share $a$, while the complement of $\{a,b\}$ is $\{c,z\}$. The correct correspondence is between a set and its own complement, not between arbitrary optimal choices.

Using the Correspondence and Avoiding a Common Error

If a minimum vertex cover is already known, taking its complement immediately gives a maximum independent set. In the other direction, a known maximum independent set yields a minimum cover by taking its complement. This is useful for converting an answer from one optimization problem into an answer to the other; it does not by itself provide a method for finding either optimum. The identity also gives a numerical check: proposed optimum sizes must add to the order of the graph.

A frequent mistake is to treat “maximum” and “maximal” as interchangeable. A maximum independent set has greatest size; a maximal independent set is one to which no vertex can be added while preserving independence. These are different conditions. For example, in the graph with vertices $\{x,y_1,y_2,y_3\}$ and edges $\{xy_1,xy_2,xy_3\}$, the singleton $\{x\}$ is maximal independent: adding any $y_i$ creates an edge inside the set. But the three leaves $\{y_1,y_2,y_3\}$ form a larger independent set, so $\{x\}$ is not maximum. The complement theorem applies to every independent set, including maximal ones, but only the complement of a maximum independent set is guaranteed to be a minimum cover.

Another error is the claim that every minimum cover and every maximum independent set chosen separately must be complements. In the triangle-with-isolated-vertex example, $\{a,b\}$ is a minimum cover and $\{a,z\}$ is a maximum independent set, but they overlap. The correction is exact: the complement of $\{a,b\}$ is the maximum independent set $\{c,z\}$, and the complement of $\{a,z\}$ is the minimum cover $\{b,c\}$. The size relation remains true for any optimal choices because each has the corresponding optimal cardinality, even if the two sets selected independently do not pair with each other.

Check Your Understanding

Use complementation carefully: state which set is being complemented, and distinguish optimal size from a particular choice of optimal set.

Let $V=\{1,2,3,4\}$ and $E=\{12,23,34\}$. If $C=\{2,3\}$, find its complement and verify the two relevant properties.
Prove directly from the definitions that the complement of a vertex cover is independent.
A graph has $9$ vertices and a minimum vertex cover of size $4$. What are $\alpha(G)$ and the size of the complement of that cover?
Can a minimum cover and a maximum independent set fail to be complements even though their sizes add to $|V|$? Explain using the triangle with an isolated vertex.
Explain why the complement of a maximal independent set need not be a minimum cover.