Two Ways to Select Vertices
Some graph questions ask for a set of vertices that touches every edge; others ask for a set of vertices that can be chosen without selecting both ends of any edge. These are different requirements, and they lead to two basic graph parameters: the size of a smallest vertex cover and the size of a largest independent set. To work with either one, begin with the edge list and check the condition edge by edge.
Throughout, graphs are finite and simple: they have no loops or multiple edges. Write \(G=(V,E)\), where \(V\) is the vertex set and \(E\) is the edge set. An edge \(uv\) has endpoints \(u\) and \(v\). The order of \(G\) is \(n=|V|\). A set \(C\subseteq V\) is a vertex cover if every edge has at least one endpoint in \(C\). A set \(I\subseteq V\) is an independent set if no edge has both endpoints in \(I\).
The conditions are local: for a cover, inspect each edge and make sure at least one endpoint was selected; for an independent set, inspect each edge and make sure its two endpoints were not both selected. Vertices that are not incident to any edge cause no difficulty for independence, and including such a vertex in a cover is never needed to cover an edge. The empty set is permitted as a candidate in both definitions. Whether it satisfies either condition depends on the graph.
Existence and Basic Checks
Proof. The full vertex set \(V\) is a vertex cover: for every edge \(uv\in E\), both endpoints \(u\) and \(v\) belong to \(V\), so at least one belongs to \(V\). The empty set \(\varnothing\) is independent: there cannot be an edge with both endpoints in \(\varnothing\), since it contains no vertices. Thus both families of candidate sets are nonempty. Since \(V\) is finite, it has only finitely many subsets. The sizes of the covers therefore have a minimum, and the sizes of the independent sets have a maximum. Every subset of \(V\) has size between \(0\) and \(|V|\), so both parameters lie in that interval. If \(V=\varnothing\), then \(E=\varnothing\) as well, and \(\varnothing\) is both a cover and an independent set; both parameters equal \(0\). \(\square\)
Proof. Let \(C\) be a vertex cover and let \(C\subseteq C'\subseteq V\). For any edge \(uv\), the cover property gives \(u\in C\) or \(v\in C\). Since \(C\subseteq C'\), that same endpoint belongs to \(C'\), so \(C'\) covers the edge. This holds for every edge. Now let \(I\) be independent and \(I'\subseteq I\). If an edge had both endpoints in \(I'\), then both would also belong to \(I\), contradicting that \(I\) is independent. Thus \(I'\) is independent. These arguments also apply when one or more of the sets is empty. \(\square\)
The propositions give useful checks but do not identify the optimum on their own. A large set may cover every edge without being a minimum cover, and a small independent set may satisfy the condition without being maximum. To establish an optimum, verify a candidate and also rule out a better size, using the specific edges of the graph.
Checking Candidate Sets
Worked Example: A Star and a Correct Cover Check
Let \(G=(V,E)\) have \(V=\{a,b,c,d\}\) and \(E=\{ac,bc,cd\}\). This is a star whose centre is \(c\). Consider the sets \(C=\{c\}\) and \(C'=\{a,b,d\}\), and also find a maximum independent set.
First check \(C=\{c\}\) against every edge. The edge \(ac\) has endpoint \(c\in C\); the edge \(bc\) has endpoint \(c\in C\); and the edge \(cd\) has endpoint \(c\in C\). Thus \(C\) is a vertex cover of size \(1\). The empty set is not a cover, because, for example, neither endpoint of the edge \(ac\) belongs to it. Hence no cover has size \(0\), and \(\tau(G)=1\).
Now check \(C'=\{a,b,d\}\). The edge \(ac\) meets \(C'\) at \(a\), the edge \(bc\) meets \(C'\) at \(b\), and the edge \(cd\) meets \(C'\) at \(d\). Therefore \(C'\) is also a vertex cover. It is not minimum: its size is \(3\), while the smaller cover \(\{c\}\) has size \(1\).
For independence, let \(I=\{a,b,d\}\). The listed edges are \(ac,bc,cd\), and none has both endpoints in \(I\), so \(I\) is independent. The only vertex not in \(I\) is \(c\), so any set of four vertices is \(V\), which contains the edge \(ac\) and is not independent. Therefore \(\alpha(G)=3\).
Check: The three edges are all covered by \(\{c\}\), and at least one vertex is necessary because \(E\) is nonempty. The three vertices \(a,b,d\) are pairwise nonadjacent, while the only larger possible set is all four vertices and that set contains adjacent endpoints. These checks confirm \(\tau(G)=1\) and \(\alpha(G)=3\).
This example illustrates why a cover must be checked by endpoints, not by whether it contains every vertex incident to an edge. A cover may omit a vertex and still cover all edges if their other endpoints are selected. Conversely, a set that includes many vertices is not automatically a minimum cover; the minimum refers to size among all covers.
Worked Example: A Four-Vertex Path
Let \(G=(V,E)\) have \(V=\{1,2,3,4\}\) and \(E=\{12,23,34\}\). We determine \(\tau(G)\) and \(\alpha(G)\) by checking candidates and excluding better sizes.
The set \(C=\{2,3\}\) covers edge \(12\) at vertex \(2\), edge \(23\) at both selected vertices, and edge \(34\) at vertex \(3\). Thus it is a cover of size \(2\). A one-vertex set cannot cover all three edges: to cover both \(12\) and \(34\), its only vertex would have to be an endpoint of both edges, but \(\{1,2\}\cap\{3,4\}=\varnothing\). The empty set also fails because \(12\in E\). Therefore no cover has size below \(2\), and \(\tau(G)=2\).
The set \(I=\{1,3\}\) is independent: edge \(12\) has only endpoint \(1\) in \(I\), edge \(23\) has only endpoint \(3\) in \(I\), and edge \(34\) has only endpoint \(3\) in \(I\). Thus an independent set of size \(2\) exists. To rule out size \(3\), list the four three-vertex subsets. The set \(\{1,2,3\}\) contains edge \(12\); \(\{1,2,4\}\) contains edge \(12\); \(\{1,3,4\}\) contains edge \(34\); and \(\{2,3,4\}\) contains edge \(23\). None is independent. Hence \(\alpha(G)=2\).
Check: The edge-by-edge checks establish that \(\{2,3\}\) covers all three edges and \(\{1,3\}\) contains no edge. The two separate lower or upper bounds show that neither parameter can have a better size: a cover of size \(1\) cannot meet both \(12\) and \(34\), and each three-vertex subset contains a listed edge.
Small Graphs with Different Structures
Worked Example: A Triangle with a Pendant Edge
Let \(G=(V,E)\) have \(V=\{a,b,c,d\}\) and \(E=\{ab,bc,ca,cd\}\). The first three edges form a triangle, and \(cd\) is an additional edge. Find a minimum vertex cover and a maximum independent set.
Take \(C=\{a,c\}\). Edge \(ab\) meets \(C\) at \(a\), edge \(bc\) at \(c\), edge \(ca\) at both endpoints, and edge \(cd\) at \(c\). Thus \(C\) is a cover of size \(2\). No single vertex covers the three triangle edges: choosing \(a\) misses \(bc\), choosing \(b\) misses \(ca\), choosing \(c\) misses \(ab\), and choosing \(d\) misses all three. The empty set also misses each triangle edge. Therefore \(\tau(G)=2\).
For an independent set, choose \(I=\{b,d\}\). The only edges incident to \(b\) are \(ab\) and \(bc\), and the only edge incident to \(d\) is \(cd\); there is no edge \(bd\). Hence no listed edge has both endpoints in \(I\), so \(I\) is independent. Any independent set can contain at most one of \(a,b,c\), because each pair among these three vertices is an edge. It can contain at most one additional vertex, namely \(d\). Therefore every independent set has size at most \(2\), and \(\alpha(G)=2\).
Check: For the cover, the four intersections with the edge endpoints are witnessed by \(a,c,c,c\), respectively; for the independent set, the complete edge list has no edge \(bd\) and no edge with both endpoints in \(\{b,d\}\). The exclusions establish that neither a one-vertex cover nor an independent set of size \(3\) is possible.
Worked Example: An Edgeless Graph
Let \(G=(V,E)\) have \(V=\{p,q,r\}\) and \(E=\varnothing\). Determine the two parameters and give sets attaining them.
The empty set is a vertex cover because there are no edges for which the cover condition could fail. Its size is \(0\), and no set has negative size, so \(\tau(G)=0\). The full set \(I=\{p,q,r\}\) is independent because there are no edges with both endpoints in it. Its size is \(3\), the number of vertices, so no larger subset of \(V\) exists and \(\alpha(G)=3\).
Check: The edge list has zero entries, so the cover condition is satisfied by \(\varnothing\) without needing any selected endpoint. Every pair of vertices is nonadjacent because no edges are listed, and the independent set has size \(|I|=3=|V|\). Thus the values \(0\) and \(3\) follow directly from the definitions.
Common Mistakes and a Reliable Procedure
Mistake: treating an omitted vertex as an uncovered edge. In the star example, it would be wrong to say that \(\{a,b,d\}\) fails to cover the graph because it omits \(c\). The cover condition is about edges, not about including every vertex. The correction is to check the edges individually: \(ac\) is covered by \(a\), \(bc\) by \(b\), and \(cd\) by \(d\). So \(\{a,b,d\}\) is a cover, although it is not minimum because \(\{c\}\) is a smaller cover.
Mistake: checking only some edges. A set is a cover only if every edge has a selected endpoint. A single missed edge disproves the claim. For independence, one edge with both endpoints selected is enough to disprove the claim. A useful routine is therefore to write the edge list and make one check for each edge.
Mistake: confusing a valid set with an optimum. Verifying that \(C\) is a cover proves only that it is a cover; it does not prove \(|C|=\tau(G)\). Likewise, verifying that \(I\) is independent does not prove \(|I|=\alpha(G)\). An optimum claim needs two parts: exhibit a set of the claimed size and show that no better size is possible. The small examples above use direct arguments tailored to their edge lists.
These notions encode two basic selection tasks. A vertex cover selects vertices so every edge is incident to a selected one; an independent set selects vertices while avoiding every adjacent pair. Their definitions apply to all finite simple graphs, including graphs with isolated vertices, graphs with no edges, and the graph with no vertices. For a new graph, state its vertex and edge sets, test candidate sets against every edge, and separate verification of the condition from proof of optimal size.
Check Your Understanding
For each question, use the given edge list explicitly. When claiming an optimum, explain why a smaller cover or a larger independent set is impossible.
- For \(V=\{1,2,3,4\}\) and \(E=\{12,13,14\}\), give a minimum vertex cover and a maximum independent set. Verify each against the edge list.
- For \(V=\{a,b,c\}\) and \(E=\{ab,bc\}\), is \(\{a,c\}\) independent? Is it a vertex cover? Justify each answer separately.
- For \(V=\{1,2,3,4\}\) and \(E=\{12,23,34,41\}\), test whether \(\{1,3\}\) is a vertex cover and whether it is independent.
- Explain why every graph with no edges has the empty set as a vertex cover, even if its vertex set is nonempty.
- Give an example of a vertex cover that is not minimum, and identify a smaller cover for the same graph.