Independent set (graph theory)

An independent set selects mutually compatible objects when an edge of a graph represents a conflict. For example, if vertices are activities and edges join activities that cannot occur together, an independent set is a collection that can share one time slot. Finding the largest such collection is measured by the independence number.^[ref]

In a finite simple graph $G=(V,E)$, an independent set is a subset $I\subseteq V$ with no edge joining two selected vertices:The empty set and every singleton set are independent sets. In the cycle graph $C_5$ drawn under vertex cover, $\{0,2\}$ is an independent set, but $\{0,4\}$ is not: the closing edge $40$ joins those two vertices. Choosing nonconsecutive labels is insufficient unless the wraparound edge is checked.

An independent set of maximum size has cardinality equal to the independence number. Being unable to add another vertex only makes an independent set inclusion-maximal. In the star graph $K_{1,3}$, the centre alone is inclusion-maximal, since it is adjacent to every leaf, but the three leaves form a larger independent set. This distinction mirrors the difference between an inclusion-minimal vertex cover and a minimum vertex cover.

Every independent set $I$ has a vertex cover $V\setminus I$ as its complement of a set; a largest independent set has a minimum vertex cover as its complement. In every proper vertex colouring, each colour class is an independent set, so graph coloring partitions the vertices into mutually compatible groups.

An independent set with the largest possible cardinality in the given finite graph. Its size is the independence number. This differs from a maximal independent set, which only cannot be enlarged by adding vertices: another independent set can still be larger.

Root a finite tree. The two dynamic programming states are the optimal size in the descendant subtree when its root $v$ is included, $I(v)$, or excluded, $O(v)$. The sums run over its children. Inclusion forces every child to be excluded; exclusion permits each child's better state. Child subtrees have no edges between them, which proves independence of these choices. The leaf states are $I=1,O=0$, and the root's better state gives the optimum.

A postorder traversal computes the states in $O(n)$ time and storage. Reconstruct a set by following an attaining root choice and the same child constraints, breaking ties arbitrarily. The empty and singleton cases use the ordinary non-strict subset convention.

An independent dominating set is simultaneously an independent set and a dominating set. Equivalently, it is an independent set maximal under inclusion: an outside vertex can be added while preserving independence exactly when it has no neighbour in the selected set. On a triangle in a graph, any singleton is an independent dominating set but no independent vertex cover exists. Independence and domination are directly expressible in first-order logic when a fixed bound on the number of selected vertices is given.

For a graph whose vertices are partitioned into parts, an independent transversal is an independent set containing exactly one vertex from each part. If a cycle's parts each have twelve vertices, choose one vertex uniformly and independently per part. A cycle edge joining distinct parts is selected at both ends with probability $1/144$. Each event depends on at most $47$ others, since each part meets at most $24$ cycle edges. The Lovász local lemma applies because $48e/144<1$, proving existence for an arbitrary such partition.

Order vertices by nonincreasing positive degrees $d_i$, and let $b_i$ count preceding neighbors. The Madiman-Tetali inequality applied to preceding-neighbor sets and $b_i$ copies of singleton $i$ bounds the entropy of a uniformly chosen independent set. In each local term, all-zero neighbor assignment permits two choices at $i$, while every other assignment permits at most one. The maximum-entropy bound gives ${\log }_2(2^{b_i+1}-1)$ for that term. Complete bipartite graphs $K_{d,d}$ attain equality when one part is ordered before the other.

The independence number is the largest cardinality of an independent set in a finite simple graph:It answers "how many mutually compatible objects can be selected at once?", while the chromatic number asks how many compatible groups are needed for all the vertices. Diestel uses this notation for a largest independent set.^[ref]

For the cycle graph $C_5$, the independent set $\{0,2\}$ shows that $\alpha (C_5)\ge 2$. Three selected vertices would require at least three unselected vertices separating them around the cycle graph, which has only five vertices. Thus $\alpha (C_5)=2$. There are five largest independent sets, obtained by rotating $\{0,2\}$ around the cycle graph, and five corresponding minimum vertex covers.

For the complete bipartite graph $K_{2,3}$, an independent set cannot contain a vertex from each side, since every such pair is joined by an edge. The larger side has three vertices, so $\alpha (K_{2,3})=3$. A triangle in a graph has independence number one. A graph with no edges and $n$ vertices has independence number $n$, including $\alpha (G)=0$ when $n=0$.

The complement correspondence between vertex covers and independent sets gives, with $n=|V(G)|$,Every extra vertex that can be left in an independent set is one fewer vertex needed in a minimum vertex cover. This identity holds for all finite simple graphs, including the triangle in a graph and the cycle graph $C_5$; it does not require the bipartite graph hypothesis of Kőnig's theorem for bipartite matching.

For a nonempty graph, every colour class of a proper vertex colouring contains at most $\alpha (G)$ vertices. Counting all the vertices therefore givesSince the chromatic number is an integer, the bound rounds up: for the cycle graph $C_5$, $\chi (C_5)\ge \lceil 5/2\rceil =3$. It is attained by assigning colour $A$ to $0,2$, colour $B$ to $1,3$, and colour $C$ to $4$. All five edges, including $40$, have differently coloured endpoints.

For a finite simple graph, $\alpha (G)\ge {\sum }_{v\in V(G)}1/(1+\mathrm{deg}v)\ge |V(G){|}^2/(|V(G)|+2|E(G)|)$. Randomly order its vertices and retain each vertex preceding all its graph neighbours. This gives an independent set with the first expression as its expected value. The second inequality is the Cauchy-Schwarz inequality.

For every sufficiently large $n$, there is a triangle-free graph $G$ on $n$ vertices with $\alpha (G)<n^{0.7}$. One construction samples $G(2n,(2n{)}^{-0.69})$: with positive probability it has fewer than $n$ triangles and no independent set of size $n^{0.7}$. Delete one vertex from each triangle and then take an induced $n$-vertex subgraph.

Every finite graph of maximum degree at most $\Delta$ has an independent set of size at least $|V|/(\Delta +1)$. Greedily choose a vertex and delete its closed neighbourhood.

There is an absolute $c>0$ such that if an $n$-vertex graph has maximum degree at most $d$ and every vertex neighbourhood spans at most $d^2/f$ edges, where $2\le f\le d^2$, thenThe triangle-free case is commonly called Shearer's independence bound.

Every triangle-free graph on $n$ vertices with maximum degree at most $d$ hasfor an absolute constant $c>0$.