= Independence number
{title2=$\alpha(G)$}
{wiki}
The <independence number> is the largest <cardinality> of an <independent set> in a finite <simple graph>:
$$
\alpha(G)=\max\{|I|:I\subseteq V(G),\ I\text{ is an independent set of }G\}.
$$
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>.<Graph Theory by Reinhard Diestel>[Diestel, Graph Theory, Chapter 2, Exercise 23]{ref}
For the <cycle graph> $C_5$, the <independent set> $\{0,2\}$ shows that $\alpha(C_5)\geq2$. 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)|$,
$$
\tau(G)+\alpha(G)=n.
$$
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 gives
$$
\chi(G)\geq\frac{|V(G)|}{\alpha(G)}.
$$
Since the <chromatic number> is an <integer>, the bound rounds up: for the <cycle graph> $C_5$, $\chi(C_5)\geq\lceil5/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.
Back to article page
