Two Opposite Ways to Describe a Vertex Set
A vertex cover and an independent set impose opposite conditions on the edges of a graph. A cover must meet every edge; an independent set must contain no pair of adjacent vertices. Taking the complement of a vertex set exchanges these conditions. This simple correspondence yields an exact relation between the smallest possible cover and the largest possible independent set.
Throughout, graphs are finite and simple. For a graph \(G=(V,E)\), write \(n=|V|\). A set \(C\subseteq V\) is a vertex cover if every edge has at least one endpoint in \(C\). A set \(S\subseteq V\) is an independent set if no edge has both endpoints in \(S\). The vertex-cover number \(\tau(G)\) is the minimum size of a vertex cover, and the independence number \(\alpha(G)\) is the maximum size of an independent set. These extrema exist because \(V\) is finite. For the graph with no vertices, the empty set is both a cover and an independent set, so \(\tau(G)=\alpha(G)=0\).
To check the first equivalence, \(C\) fails to be a cover exactly when some edge has neither endpoint in \(C\). Both endpoints of that edge then belong to \(V\setminus C\), so \(V\setminus C\) is not independent. Conversely, if \(V\setminus C\) contains both endpoints of an edge, that edge is not met by \(C\), so \(C\) is not a cover. The second equivalence is the same statement with \(S=V\setminus C\).
The Vertex-Cover and Independence Identity
Proof. Let \(C\) be a minimum vertex cover, so \(|C|=\tau(G)\). By the key observation, \(V\setminus C\) is independent and has size \(n-\tau(G)\). Therefore \(\alpha(G)\ge n-\tau(G)\), which gives \(\tau(G)+\alpha(G)\ge n\). Now let \(S\) be a maximum independent set, so \(|S|=\alpha(G)\). Its complement \(V\setminus S\) is a vertex cover of size \(n-\alpha(G)\). Thus \(\tau(G)\le n-\alpha(G)\), giving \(\tau(G)+\alpha(G)\le n\). Combining the two inequalities proves the identity. If \(V=\varnothing\), both parameters are \(0\), and the same equality holds. \(\square\)
The proof also specifies exactly how optimal sets convert. The complement of every minimum vertex cover is a maximum independent set: it is independent and has size \(n-\tau(G)=\alpha(G)\). Likewise, the complement of every maximum independent set is a minimum vertex cover. The word “every” matters: taking a complement always produces a set of the other type, but it produces an optimal set only when the original set is optimal.
For a vertex cover \(C\), form \(S=V\setminus C\). No edge can have both endpoints in \(S\), so \(S\) is independent.
For an independent set \(S\), form \(C=V\setminus S\). Every edge must have an endpoint in \(C\), so \(C\) is a vertex cover.
For either conversion, the new set has size \(n\) minus the size of the original set. A smallest cover therefore corresponds to a largest independent set, and vice versa.
Worked Conversions
Worked Example: A Three-Vertex Path
Let \(G\) have vertex set \(V=\{1,2,3\}\) and edge set \(E=\{12,23\}\). Find its minimum vertex-cover size and maximum independent-set size, and convert sets in both directions.
The set \(\{2\}\) is a cover: edge \(12\) has endpoint \(2\), and edge \(23\) also has endpoint \(2\). No empty set covers either edge, so \(\tau(G)=1\). Its complement is \(\{1,3\}\), which is independent because the only edges are \(12\) and \(23\); neither is an edge between \(1\) and \(3\).
To check that \(\{1,3\}\) is maximum, an independent set cannot contain both endpoints of either edge. The two-vertex set \(\{1,3\}\) is independent, while the three-vertex set \(V\) is not, since it contains both endpoints of \(12\). Thus \(\alpha(G)=2\). The identity checks numerically: \(1+2=3=|V|\).
The reverse conversion works as well: the complement of the maximum independent set \(\{1,3\}\) is the minimum cover \(\{2\}\). But the independent set \(\{1\}\) is not maximum. Its complement \(\{2,3\}\) is a cover of size \(2\), not a minimum cover. This illustrates why the identity applies to the maximum independent-set size, not to the size of every independent set.
Worked Example: A Triangle with a Pendant Edge
Let \(G\) have \(V=\{a,b,c,d\}\) and \(E=\{ab,bc,ca,cd\}\). The vertices \(a,b,c\) form a triangle, and \(cd\) is an additional edge. Determine \(\alpha(G)\) and \(\tau(G)\), with complementary sets that attain them.
An independent set contains at most one of \(a,b,c\), since every pair among them is an edge. It can contain at most one further vertex, namely \(d\). Hence every independent set has size at most \(2\). The set \(\{a,d\}\) is independent: \(ad\notin E\), and it contains no other pair. Therefore \(\alpha(G)=2\). Its complement \(\{b,c\}\) is a cover: \(ab\) meets \(b\), \(bc\) meets both selected vertices, \(ca\) meets \(c\), and \(cd\) meets \(c\).
A cover of the triangle must contain at least two of \(a,b,c\). If it contained at most one, the edge between the other two triangle vertices would be uncovered. Thus every cover of \(G\) has size at least \(2\). The set \(\{b,c\}\), already checked, is a cover of size \(2\), so \(\tau(G)=2\). The identity gives \(2+2=4=|V|\).
For another direct conversion, \(\{a,c\}\) is a cover: it meets \(ab\) at \(a\), \(bc\) at \(c\), \(ca\) at both endpoints, and \(cd\) at \(c\). Its complement \(\{b,d\}\) is independent because \(bd\notin E\). Both conversions here produce optimal sets, as their sizes are \(2\) and \(4-2=2\).
Worked Example: Isolated Vertices and Disconnected Edges
Let \(G\) have \(V=\{1,2,3,4,5\}\) and \(E=\{12,34\}\). Vertices \(1,2\) form one component, vertices \(3,4\) form another, and vertex \(5\) is isolated. Find optimal sets and verify the identity.
An independent set can contain at most one vertex from \(\{1,2\}\), and at most one from \(\{3,4\}\), because \(12\) and \(34\) are edges. It can also contain vertex \(5\), which is incident to no edge. Thus its size is at most \(1+1+1=3\). The set \(\{1,3,5\}\) is independent: it contains neither the pair \(1,2\) nor the pair \(3,4\). Consequently \(\alpha(G)=3\).
Every cover must include at least one endpoint of edge \(12\) and at least one endpoint of edge \(34\). These edges have no common endpoint, so at least two vertices are needed. The set \(\{2,4\}\) covers both edges, and no other edges need to be covered. Hence \(\tau(G)=2\). The complement of \(\{2,4\}\) is \(\{1,3,5\}\), and \(2+3=5=|V|\). The isolated vertex belongs to a maximum independent set and need not belong to a minimum cover.
What an Arbitrary Set Tells You
The complement correspondence gives useful inequalities even before an optimum is known. If \(S\) is any independent set of size \(r\), then \(V\setminus S\) is a cover of size \(n-r\). Therefore $$ \tau(G)\le n-r. $$ Equality follows when \(S\) is maximum, because then \(r=\alpha(G)\) and the identity gives \(\tau(G)=n-\alpha(G)\). For a nonmaximum independent set, the complement can be larger than a minimum cover.
Similarly, if \(C\) is any vertex cover of size \(q\), then \(V\setminus C\) is an independent set of size \(n-q\), so \(\alpha(G)\ge n-q\). Equality holds when \(C\) is minimum. These statements keep the direction of the inequality attached to the set actually chosen.
Common Pitfall: Treating Any Independent Set as Maximum
In the three-vertex path, take the independent set \(S=\{1\}\). Its size is \(r=1\), and \(n-r=3-1=2\). The complement \(\{2,3\}\) is indeed a vertex cover, but the minimum cover is \(\{2\}\), so \(\tau(G)=1\), not \(2\). The valid conclusion from this particular \(S\) is only \(\tau(G)\le 2\). To conclude \(\tau(G)=n-r\), one must know that \(S\) is maximum; here \(\{1,3\}\) is maximum and its complement \(\{2\}\) has size \(3-2=1\).
The identity is useful because it lets an optimal solution be described in either language. A graph with a large independent set has a small complementary cover, and a graph whose minimum cover is small has a large complementary independent set. It also supplies a consistency check for calculations: once one of \(\tau(G)\) or \(\alpha(G)\) is known, the other must be \(n\) minus that value. The complement argument applies to disconnected graphs and isolated vertices without modification; it depends only on which pairs are edges.
Check Your Understanding
For each question, use the complement correspondence and distinguish arbitrary sets from optimal ones.
- If \(G\) has \(11\) vertices and \(\alpha(G)=7\), what is \(\tau(G)\)? State which theorem justifies the calculation.
- In a graph with \(n\) vertices, an independent set has size \(r\). What inequality does this imply for \(\tau(G)\), and when can it be replaced by equality?
- Prove directly from the definitions that the complement of a vertex cover is independent.
- For \(V=\{1,2,3,4\}\) and \(E=\{12,23,34\}\), give an independent set and its complementary cover. Are both necessarily optimal? Justify your answer.
- Explain why an isolated vertex can be included in an independent set without preventing it from being independent, and why it is not needed to cover any edge.