Two Different Meanings of “Best”
In graph problems, a set can be impossible to enlarge without losing a property, yet still be far from having the largest possible size. This distinction matters for independent sets and vertex covers: maximal and minimal describe inclusion, while maximum and minimum describe cardinality. Confusing these terms can turn a correct local observation into an incorrect claim about an optimum.
Throughout, graphs are finite and simple. A set \(S\subseteq V(G)\) is independent if no edge has both endpoints in \(S\). A set \(C\subseteq V(G)\) is a vertex cover if every edge has at least one endpoint in \(C\).
Maximality and minimality ask whether a set can be changed by inclusion: can an independent set be enlarged, or can a cover be reduced? Maximum and minimum ask a global size question: is there any independent set larger, or any cover smaller? Since the graph is finite, maximum independent sets and minimum vertex covers exist. They need not be the only sets of their respective sizes.
Complementation Reverses the Inclusion Relation
The key link is taking the complement of a vertex set within \(V(G)\). If \(S\subseteq V(G)\), write \(V(G)\setminus S\) for the vertices not in \(S\). An edge fails to meet this complement exactly when both its endpoints lie in \(S\). This gives the basic correspondence.
Proof. Let \(C=V(G)\setminus S\). If \(S\) is independent, no edge has both endpoints in \(S\). Therefore every edge has at least one endpoint outside \(S\), which means it has an endpoint in \(C\); hence \(C\) is a vertex cover. Conversely, if \(C\) is a vertex cover, no edge can have both endpoints outside \(C\). Since the vertices outside \(C\) are exactly \(S\), no edge has both endpoints in \(S\), so \(S\) is independent.
The complement operation is a bijection: taking the complement twice returns the original set. It also reverses inclusion. If \(S\subsetneq T\), then \(V(G)\setminus T\subsetneq V(G)\setminus S\). Thus an independent set \(S\) has a proper independent superset exactly when its complementary cover has a proper subset that is still a cover. This proves the maximal–minimal correspondence in both directions.
For the size statement, let \(n=|V(G)|\). Every set and its complement have sizes adding to \(n\): \(|V(G)\setminus S|=n-|S|\). Thus a larger independent set corresponds to a smaller vertex cover, and a largest independent set corresponds to a smallest cover. Conversely, a smallest cover must have a largest complementary independent set. This proves the maximum–minimum correspondence in both directions. The argument also applies when \(V(G)=\varnothing\): the empty set is both independent and a cover, and is its own complement. \(\square\)
In the notation for graph parameters, the maximum size of an independent set is \(\alpha(G)\), and the minimum size of a vertex cover is \(\tau(G)\). The correspondence gives \(\alpha(G)+\tau(G)=|V(G)|\). It does not say that every maximal independent set has size \(\alpha(G)\), or that every minimal cover has size \(\tau(G)\).
A Local Test for Maximality
Maximality can be checked by considering vertices outside the set, rather than searching through all independent sets. A vertex \(v\) is a neighbor of \(u\) when \(uv\in E(G)\).
Proof. Suppose \(S\) is independent and maximal. If some vertex \(v\notin S\) had no neighbor in \(S\), then adding \(v\) would create no edge with both endpoints in \(S\cup\{v\}\). This would be a larger independent set, contradicting maximality. Conversely, suppose every vertex outside \(S\) has a neighbor in \(S\). Any proper superset of \(S\) contains some vertex \(v\notin S\), and the edge from \(v\) to a vertex in \(S\) prevents that superset from being independent. Therefore \(S\) is maximal.
For the cover statement, put \(S=V(G)\setminus C\). By the theorem, \(C\) is a minimal cover exactly when \(S\) is a maximal independent set. The condition just proved says every vertex outside \(S\)—that is, every vertex in \(C\)—has a neighbor in \(S=V(G)\setminus C\). This proves the equivalent condition for minimal covers as well. \(\square\)
This test includes isolated vertices correctly. An isolated vertex cannot lie outside a maximal independent set, because it has no neighbor in the set and could be added. It cannot lie in a minimal vertex cover either, because no edge needs it to cover.
Worked Example: A Path with Three Vertices
Let \(G\) have vertex set \(V(G)=\{1,2,3\}\) and edge set \(E(G)=\{12,23\}\). The set \(\{2\}\) is independent. It is maximal: each vertex outside it, namely \(1\) and \(3\), has a neighbor in it. Its size is \(1\).
The set \(\{1,3\}\) is also independent, because the edge set contains neither \(13\) nor any other edge with both endpoints in \(\{1,3\}\). It is maximal because the only remaining vertex, \(2\), has a neighbor in the set. It is maximum: an independent set containing \(2\) cannot contain either \(1\) or \(3\), while a set not containing \(2\) has at most the two vertices \(1\) and \(3\). Thus \(\alpha(G)=2\), whereas the maximal independent set \(\{2\}\) has size \(1\).
The complements illustrate the corresponding cover distinction. The complement of \(\{1,3\}\) is \(\{2\}\), a minimum vertex cover of size \(1\), since it meets both edges. The complement of \(\{2\}\) is \(\{1,3\}\). This is a minimal vertex cover: removing \(1\) leaves edge \(12\) uncovered, and removing \(3\) leaves edge \(23\) uncovered. Its size is \(2\), so it is not minimum. The values check the identity: \(\alpha(G)+\tau(G)=2+1=3=|V(G)|\).
Different Maximal Sets Can Have Different Sizes
It is not just that a maximal set may be smaller than a maximum set. A single graph can have several maximal independent sets of different sizes. The same is then true of its minimal vertex covers, with sizes reversed by complementation.
Worked Example: A Five-Vertex Path
Let \(G\) have \(V(G)=\{1,2,3,4,5\}\) and \(E(G)=\{12,23,34,45\}\). The set \(S=\{2,4\}\) is independent: none of the four listed edges has both endpoints in \(S\). It is maximal because the outside vertices \(1,3,5\) each have a neighbor in \(S\): \(1\) is adjacent to \(2\), \(3\) to \(2\) and \(4\), and \(5\) to \(4\). So this maximal independent set has size \(2\).
Now \(T=\{1,3,5\}\) is independent, as no listed edge joins two of its vertices. It is maximum. To see the upper bound, split the vertices into the pairs \(\{1,2\}\), \(\{3,4\}\), and the singleton \(\{5\}\). Each pair is an edge, so an independent set contains at most one vertex from each pair; it contains at most the singleton as well. Hence every independent set has size at most \(3\), and \(T\) attains \(3\). Thus the graph has maximal independent sets of sizes \(2\) and \(3\), with \(\alpha(G)=3\).
The complement of \(S\) is \(C=\{1,3,5\}\), a minimal cover of size \(3\). Each vertex of \(C\) has a neighbor outside \(C\): the edges \(12\), \(34\), and \(45\) show this for \(1\), \(3\), and \(5\), respectively. The complement of the maximum set \(T\) is \(\{2,4\}\), which covers all four edges and has size \(2\). It is minimum: the two disjoint edges \(12\) and \(45\) require at least two cover vertices, and \(\{2,4\}\) has exactly two. The sizes also satisfy \(3+2=5=|V(G)|\).
Worked Example: A Triangle with a Pendant Edge
Let \(G\) have \(V(G)=\{1,2,3,4\}\) and \(E(G)=\{12,23,31,34\}\). The set \(\{3\}\) is independent and maximal: each outside vertex \(1,2,4\) is adjacent to \(3\). Its size is \(1\).
The set \(\{1,4\}\) is independent, since no edge joins \(1\) to \(4\). It is maximum. Among the triangle vertices \(1,2,3\), an independent set can contain at most one, because each pair is an edge. If it contains \(3\), it cannot also contain \(4\), as \(34\) is an edge; if it contains \(1\) or \(2\), it can contain \(4\). Therefore an independent set has size at most \(2\), and \(\{1,4\}\) attains that size. Thus \(\alpha(G)=2\), while the maximal independent set \(\{3\}\) has size \(1\).
The complement \(\{1,2,4\}\) of \(\{3\}\) is a minimal cover of size \(3\): each of its vertices has a neighbor outside the cover, namely vertex \(3\). The complement \(\{2,3\}\) of the maximum independent set \(\{1,4\}\) is a cover of size \(2\). It is minimum because the correspondence gives its size as \(|V(G)|-\alpha(G)=4-2=2\). Hence this graph has a minimal cover larger than a minimum cover.
Common Mistake and Why the Distinction Matters
Wrong calculation: In the three-vertex path, \(\{2\}\) is maximal independent and has size \(1\), so one might conclude \(\alpha(G)=1\). That conclusion confuses “cannot be enlarged” with “has largest size.” The correction is to compare with other independent sets: \(\{1,3\}\) is independent and has size \(2\), so \(\alpha(G)=2\). By complementation, \(\{1,3\}\) is a minimal cover of size \(2\), but not a minimum cover; \(\{2\}\) is minimum.
In applications, a maximal independent set can represent a collection to which no further compatible item can be added. That may be useful when a locally complete selection is enough, but it does not guarantee the largest possible selection. Similarly, a minimal cover cannot lose any of its vertices while remaining a cover, but it need not use as few vertices as possible. Always check whether the question asks for an inclusion condition or an optimal cardinality.
The complement theorem translates either kind of question: finding a maximum independent set is equivalent to finding a minimum vertex cover, and finding a maximal independent set corresponds to finding a minimal vertex cover. The local neighborhood test can certify maximality or minimality, but by itself it does not establish that the set has an optimal size.
Check Your Understanding
For each question, keep inclusion and cardinality separate, and use complements where appropriate.
- Give a graph with a maximal independent set that is not maximum, and verify both properties.
- Prove directly that if \(S\) is a maximum independent set, then \(V(G)\setminus S\) is a minimum vertex cover.
- In the five-vertex path example, explain why the partition into two edges and one singleton gives an upper bound of \(3\) on the size of every independent set.
- Show that every maximal independent set contains every isolated vertex.
- Can two maximal independent sets in one graph have different sizes? Give an example and state the sizes.