Lovasz's numerical criterion for perfect graphs and complement invariance

If $G$ is perfect, color each induced $H$ with $\omega (H)$ colors. Each color class is stable and has at most $\alpha (H)$ vertices, so $\mathrm{\mid }V(H)\mathrm{\mid }\le \alpha (H)\omega (H)$. This includes the empty graph, for which both sides are zero.

Conversely, assume the numerical inequality for every induced subgraph of $G$ and induct on $n=\mathrm{\mid }V(G)\mathrm{\mid }$. It passes to each proper induced subgraph, so those subgraphs are perfect by induction. The empty case is immediate. Suppose for contradiction that nonempty $G$ is not perfect. Put $a=\alpha (G)$, $w=\omega (G)$ and $d=aw+1$. Then $\chi (G)>w$, while the assumed inequality gives $n\le aw=d-1$.

If $U\subseteq V(G)$ is a nonempty stable set, then $G-U$ is a proper perfect induced subgraph. It must have a $w$-clique: otherwise $\chi (G-U)=\omega (G-U)\le w-1$, and coloring $U$ with one new color would give $\chi (G)\le w$, contrary to step 1.2. This also covers $G-U$ empty.

Fix a maximum stable set $A_0=\{u_1,\dots ,u_a\}$. For each $i$, choose an optimal $w$-coloring of $G-u_i$, possible by step 2.1 and perfection of that proper induced subgraph. Name its $w$ color classes $A_{(i-1)w+1},\dots ,A_{iw}$. Thus $A_0,A_1,\dots ,A_{aw}$ are $d=aw+1$ stable sets. By step 2.1, for each $j\in \{0,\dots ,aw\}$ fix a $w$-clique $K_j$ in $G-A_j$. All selections are from finite families.

Let $K$ be any $w$-clique of $G$. If $K\cap A_0=\mathrm{\varnothing }$, then for every $i$ it is a $w$-clique of $G-u_i$ and meets each of that graph's $w$ color classes exactly once. If $K\cap A_0=\{u_i\}$, then it meets $A_0$ once; in the $i$th coloring, its other $w-1$ vertices occupy exactly $w-1$ of the $w$ color classes, so it misses exactly one class in that block. For each other $u_h\in A_0$ it meets all $w$ classes of the $h$th coloring. A clique meets $A_0$ at most once. Therefore $K$ is disjoint from exactly one of $A_0,\dots ,A_{aw}$ and meets every other one in exactly one vertex. In particular, $\mathrm{\mid }{A}_i\cap K_j\mathrm{\mid }=0$ if $i=j$ and $1$ if $i\mathrm{\ne }j$.

Enumerate $V(G)=\{v_1,\dots ,v_n\}$. Let $A$ be the real $d\times n$ matrix whose $i$th row is the incidence vector of $A_i$, and let $B$ be the real $n\times d$ matrix whose $j$th column is the incidence vector of $K_j$. By step 4.1, $AB=J_d-I_d$: its diagonal entries are $0$ and all off-diagonal entries are $1$. This $d\times d$ matrix has independent columns. Indeed, if $(J_d-I_d)z=0$, put $s={\sum }_i{z}_i$. Each coordinate equation says $s-z_i=0$, so all $z_i=s$; then $s=ds$, and $d\ge 2$ forces $s=0$ and $z=0$. Hence the $d$ columns of $B$ are independent: any linear relation among them would remain a relation after multiplying by $A$. But $d>n$ by step 1.2, contradicting [L3] for vectors of ${\mathbb{R}}^n$.

The contradiction discharges step 1.2, proving the numerical criterion. If $G$ is perfect, step 1.1 gives the inequality for every induced $H$. For each induced subgraph $\bar{H}$ of $\bar{G}$, [L2] gives $\mathrm{\mid }V(\bar{H})\mathrm{\mid }=\mathrm{\mid }V(H)\mathrm{\mid }$, $\alpha (\bar{H})=\omega (H)$, and $\omega (\bar{H})=\alpha (H)$; so the same inequality holds in $\bar{G}$. The criterion makes $\bar{G}$ perfect. Applying that direction to $\bar{G}$ proves the converse, because $\overline{\stackrel{‾}{G}}=G$.