Independent Set — Definition, Formula & Examples

An independent set is a collection of vertices in a graph such that no two vertices in the collection are connected by an edge. In other words, every vertex in the set is non-adjacent to every other vertex in the set.

Given a graph $G = (V, E)$ , a subset $S \subseteq V$ is an independent set if for every pair of vertices $u, v \in S$ , the edge $\{u, v\} \notin E$ . The independence number $\alpha(G)$ is the cardinality of a maximum independent set in $G$ .

Key Formula

\alpha(G) = |V| - \beta(G)

Where:

$\alpha(G)$ = Independence number — size of the maximum independent set
$|V|$ = Total number of vertices in the graph
$\beta(G)$ = Size of the minimum vertex cover (by König–Gallai theorem)

How It Works

To check whether a subset of vertices forms an independent set, examine every pair of vertices in the subset and verify that no edge connects them. Finding a maximum independent set — one with the largest possible number of vertices — is NP-hard in general, meaning no known efficient algorithm solves it for all graphs. For small graphs, you can inspect candidate subsets directly. For special graph families like bipartite graphs, the maximum independent set can be found in polynomial time using König's theorem.

Worked Example

Problem: Consider the cycle graph

C_5

with vertices

\{1, 2, 3, 4, 5\}

and edges

\{1,2\}, \{2,3\}, \{3,4\}, \{4,5\}, \{5,1\}

. Find a maximum independent set.

Step 1: Try selecting non-adjacent vertices. Pick vertex 1. Its neighbors are 2 and 5, so exclude those.

S = \{1\}

Step 2: From the remaining vertices

\{3, 4\}

, pick vertex 3. Its neighbor 4 is the only remaining candidate, but 3 and 4 share an edge, so exclude 4.

S = \{1, 3\}

Step 3: Check: vertices 1 and 3 are not connected by an edge. No three mutually non-adjacent vertices exist in

C_5

(you can verify by trying all

\binom{5}{3} = 10

triples).

\alpha(C_5) = 2

Answer: A maximum independent set is

\{1, 3\}

(or equivalently

\{1, 4\}

\{2, 4\}

\{2, 5\}

, or

\{3, 5\}

), and the independence number is

\alpha(C_5) = 2

Why It Matters

Independent sets appear in scheduling problems where conflicting tasks (edges) must not overlap — selecting the most tasks with no conflicts is exactly finding a maximum independent set. The concept is also central to graph coloring, since each color class in a proper coloring forms an independent set.

Common Mistakes

Mistake: Confusing an independent set with a clique.

Correction: A clique is the opposite: every pair of vertices IS connected by an edge. An independent set requires that NO pair is connected. The independent sets of

G

are exactly the cliques of the complement graph

\bar{G}