Exercise 959Combinatorics › Graph theoryL1Added 3 Nov 2026

Cliques and independent sets

#clique#independent set#complement

Statement

Show that the clique number $\omega(G)$ equals the independence number of the complement, $\alpha(\overline{G})$ .

Hint

A clique in $G$ corresponds to a set of pairwise non-adjacent vertices in $\overline{G}$ , i.e. an independent set.

Show solutionHide solution

Solution

Clique in $G$ . $C$ is a clique in $G$ iff every pair in $C$ is adjacent in $G$ , iff every pair in $C$ is non-adjacent in $\overline{G}$ , iff $C$ is independent in $\overline{G}$ .

Conclusion. $\omega(G)=\alpha(\overline{G})$ .

Cliques and independent sets

Statement

Solution

More problems in Graph theory