Independent set

An independent set is a set of vertices no two of which are adjacent. In every proper colouring, each colour class is an independent set.

The independence number is the largest cardinality of an independent set in a graph. Since every colour class is independent,

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$.