Two Optimization Questions About Vertex Sets
Given a graph, two basic questions ask how large a set of vertices can be while satisfying opposite edge conditions. An independent set avoids every edge within the set; a clique contains every possible edge within the set. The largest sizes are useful exact parameters: they describe the best possible outcome, not merely the size of a set that happens to meet the condition.
All graphs in this tutorial are finite and simple. Thus an edge joins two distinct vertices, and there is at most one edge between any pair. For a vertex set \(S\subseteq V(G)\), the induced subgraph \(G[S]\) consists of the vertices in \(S\) and all edges of \(G\) whose two endpoints lie in \(S\). This lets us express the two edge conditions by looking only at the edges inside \(S\).
The empty set is independent and is also a clique: each condition concerns pairs of distinct vertices, and there are no such pairs in the empty set. If \(G\) has no vertices, then \(\alpha(G)=\omega(G)=0\). If \(G\) has at least one vertex, a singleton is both independent and a clique, so both parameters are at least \(1\).
Proof. The set \(V\) is finite, so it has finitely many subsets. The empty subset is an independent set and a clique, so each of the two families of qualifying subsets is nonempty. A nonempty finite family of integer sizes has a largest member, and that member is the size of one of the subsets in the family. By the definitions, the subsets qualifying for the first family are exactly the independent sets, and those qualifying for the second are exactly the cliques. Therefore the two largest sizes are attained and equal \(\alpha(G)\) and \(\omega(G)\), respectively. \(\square\)
This proposition explains the basic verification strategy. To prove a lower bound, exhibit a qualifying set of that size. To prove an upper bound, show that no larger set can qualify. When a graph is small, checking all candidates of the next possible size can be an effective way to establish that upper bound.
Worked Computations
Worked Example: A Triangle with a Tail
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5\}\) and \(E=\{12,13,23,34,45\}\). Compute \(\alpha(G)\) and \(\omega(G)\).
The set \(\{1,4\}\) is independent because \(14\notin E\), so \(\alpha(G)\ge2\). To rule out an independent set of size at least \(3\), it suffices to check every triple: any set of size at least \(3\) contains a triple, and every subset of an independent set is independent. The ten triples and an edge each contains are:
| Triple | Edge within the triple |
|---|---|
| \(\{1,2,3\}\) | \(12\) |
| \(\{1,2,4\}\) | \(12\) |
| \(\{1,2,5\}\) | \(12\) |
| \(\{1,3,4\}\) | \(13\) |
| \(\{1,3,5\}\) | \(13\) |
| \(\{1,4,5\}\) | \(45\) |
| \(\{2,3,4\}\) | \(23\) |
| \(\{2,3,5\}\) | \(23\) |
| \(\{2,4,5\}\) | \(45\) |
| \(\{3,4,5\}\) | \(34\) (also \(45\)) |
These are all \(\binom{5}{3}=10\) triples, and each contains an edge. Hence there is no independent triple or larger independent set, so \(\alpha(G)=2\). The displayed set \(\{1,4\}\) also cannot be enlarged by one vertex: \(2\) and \(3\) are adjacent to \(1\), while \(5\) is adjacent to \(4\).
The vertices \(\{1,2,3\}\) form a clique because all three edges \(12,13,23\) are present. No larger clique exists. A clique containing \(5\) can contain at most one other vertex because the only neighbor of \(5\) is \(4\). A clique containing \(4\) but not \(5\) can contain at most one other vertex because the only neighbor of \(4\) among \(\{1,2,3\}\) is \(3\). Any clique containing neither \(4\) nor \(5\) is contained in \(\{1,2,3\}\). Therefore \(\omega(G)=3\).
Check: the independent set \(\{1,4\}\) has size \(2\), and the complete triple \(\{1,2,3\}\) has size \(3\). The exhaustive triple check rules out a larger independent set, and the neighbor restrictions rule out a clique larger than the displayed triangle.
Worked Example: The Path on Five Vertices
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,45\}\). Compute both parameters.
The set \(\{1,3,5\}\) is independent: none of \(13,15,35\) is an edge. Thus \(\alpha(G)\ge3\). To prove that no independent set has size \(4\), list each four-vertex subset, identified by its omitted vertex, and an edge it contains.
| Omitted vertex | Four-vertex subset | Edge in the subset |
|---|---|---|
| \(1\) | \(\{2,3,4,5\}\) | \(23\) |
| \(2\) | \(\{1,3,4,5\}\) | \(34\) |
| \(3\) | \(\{1,2,4,5\}\) | \(12\) |
| \(4\) | \(\{1,2,3,5\}\) | \(12\) |
| \(5\) | \(\{1,2,3,4\}\) | \(12\) |
These are all five four-vertex subsets. Each contains an edge, so none is independent. A five-vertex independent set would contain a four-vertex independent subset, which is also impossible. It follows that \(\alpha(G)=3\).
The edge \(12\) is a clique of size \(2\). There is no clique of size \(3\): a vertex in a triangle would have two adjacent neighbors. The neighbors of \(2,3,4\) are, respectively, \(\{1,3\},\{2,4\},\{3,5\}\), and in each case those two neighbors are not adjacent. Vertices \(1\) and \(5\) each have only one neighbor, so neither can lie in a triangle. Thus \(\omega(G)=2\).
Check: the independent triple has size \(3\), while every four-vertex subset has an edge. The edge \(12\) gives a clique of size \(2\), and the absence of a triangle rules out any larger clique.
Worked Example: A Five-Cycle and an Isolated Vertex
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5,6\}\) and \(E=\{12,23,34,45,51\}\). The vertices \(1,\ldots,5\) form a cycle, and \(6\) is isolated, meaning it has no incident edge. Compute \(\alpha(G)\) and \(\omega(G)\).
The set \(\{2,4,6\}\) is independent: \(24\notin E\), and no edge is incident to \(6\). Therefore \(\alpha(G)\ge3\). For the upper bound, consider an independent set \(S\) among the cycle vertices \(1,\ldots,5\). If \(S\) has \(k\ge1\) vertices, arrange them in cyclic order. Between each chosen vertex and the next chosen vertex in that order, there must be at least one unchosen cycle vertex; otherwise those two chosen vertices would be adjacent. These \(k\) gaps are disjoint, so the cycle has at least \(k\) chosen and \(k\) unchosen vertices. Hence \(5\ge2k\), which implies \(k\le2\). If \(S\) is empty, the same upper bound \(k\le2\) holds. Adding the isolated vertex can increase the size by at most one, so every independent set in \(G\) has size at most \(3\). Consequently, \(\alpha(G)=3\).
The edge \(12\) is a clique of size \(2\). No three cycle vertices form a clique: for each cycle vertex, its two neighbors are not adjacent to one another, so no triangle contains that vertex. Vertex \(6\) cannot belong to a clique of size \(2\) or more because it has no neighbors. Every clique therefore has size at most \(2\), and \(\omega(G)=2\).
Check: the exhibited independent set has size \(3\), and the gap count limits any independent set on the cycle to at most \(2\) cycle vertices. The isolated vertex adds at most one. The graph has an edge but no triangle, giving clique number \(2\).
What a Maximum Set Does—and Does Not—Mean
The word maximum refers to size: a maximum independent set has size \(\alpha(G)\), and a maximum clique has size \(\omega(G)\). A different word, maximal, refers to inclusion. An independent set is maximal if no vertex can be added while keeping it independent. A clique is maximal if no vertex can be added while keeping it a clique. A maximal set need not have maximum size.
For a direct example, let \(H=(V,E)\) have \(V=\{1,2,3\}\) and \(E=\{12,23\}\). The independent set \(\{2\}\) is maximal: adding \(1\) would include edge \(12\), and adding \(3\) would include edge \(23\). But \(\{1,3\}\) is independent and has size \(2\), so \(\{2\}\) is not maximum. In fact, \(\alpha(H)=2\), since \(\{1,3\}\) attains size \(2\) and no subset of a three-vertex graph can be an independent set of size \(3\) when edges \(12\) and \(23\) are present.
These parameters are central in extremal graph questions because they turn a structural condition into a precise optimization problem. The independence number asks for the largest set avoiding edges; the clique number asks for the largest set containing all pairwise edges. In small graphs, explicit edge lists make the conditions checkable. In larger arguments, the same definitions let us ask for bounds or compare a constructed set with every possible competitor. The key discipline remains the same: verify the exhibited set, then justify the upper bound separately.
Common errors include checking only some of the candidate subsets in an exhaustive upper-bound argument, forgetting that a larger set contains smaller subsets, and treating a locally unextendable set as automatically largest. The first two worked examples show how to close an exhaustive check: enumerate every triple or every four-vertex subset, state the edge witness in each, and use the fact that every subset of an independent set remains independent. For cliques, a lower-bound example must list all pairwise edges inside the candidate set, not just some of them.
Check Your Understanding
For each question, distinguish the exhibited lower bound from the argument needed to establish an exact value.
- For the graph with \(V=\{a,b,c,d\}\) and \(E=\{ab,bc,cd\}\), give an independent set of size \(2\) and a clique of size \(2\). What additional checks establish the exact values?
- Explain why checking every three-vertex subset is enough to rule out independent sets of size at least \(3\).
- Give an example of a maximal independent set that is not maximum, and state both sizes.
- For a graph with one vertex and no edges, find \(\alpha(G)\) and \(\omega(G)\). Explain why the empty set does not determine either maximum.
- In the five-cycle example, why does each gap between consecutive chosen cycle vertices contain an unchosen vertex when the chosen set is independent?