# Prove all perfect graphs are normal.

A graph $$G$$ is perfect if for all induced subgraphs $$G'$$, $$\omega(G')=\chi(G')$$.

A graph is normal if there exists a family of independent sets $$A=\{A_1, A_2, \dots, A_p\}$$ and a family of cliques $$B=\{B_1,B_2,\dots,B_q\}$$ such that $$A_i \cap B_j \neq \emptyset$$ for all $$i,j$$ and $$A$$ and $$B$$ both cover the vertex set.

I need to show that any given perfect graph is normal.

At first, I tried letting some perfect graph be given and construct the cliques and independent sets using the property of perfectness:

Given a perfect graph G, color it properly with $$\chi(G)=\omega(G)=r$$ colors. The goal was to let the color classes be the independent sets and adjust them during the following process. Take $$B_1$$ be the largest clique of $$G$$. Since $$G$$ is perfect, this clique intersects every given independent set. "Delete" this clique and take the next largest clique to construct $$B_2$$. If this clique does not intersect one of the color classes, then there are two cases: If one of the vertices is not incident to the missing color, then color that vertex the missing color as well. If every vertex is incident to the missing color, then I am stuck. If each vertex is incident to the same vertex colored the missing color, then that vertex can be included into the clique. However, if, say, there are two vertices with the missing color, each incident to half the clique, then I do not know how to go from there.

My next instinct was indction on edges, but there it is not always true that adding or removing and edge preserves perfectness.

Next was induction on vertices, but I have not even began to make any headway there.

Any ideas?