Why are chordal graphs always perfect graphs?

Question

Chordal graphs are always perfect graphs, but I am not sure exactly why. How does the chord make sure that the graph cant be imperfect?

Answer 1

This is due to the Strong perfect graph theorem.

A hole is an induced cycle of length at least four. Its complement is called antihole. We call an hole odd if it has an odd number of vertices, and even otherwise.

Now, the Strong perfect graph theorem states, that a graph is perfect if and only if it contains no odd hole and no odd antihole.

Therefore, it is sufficient to show that a chordal graph $G$ contains no odd hole or odd antihole as an induced subgraph. $G$ clearly contains no odd hole, since the largest cycle in $G$ is a triangle. Suppose that $G$ contains an odd anti-hole. First observe, that the complement of $C_5$ (the odd hole of length $5$) is isomorphic to $C_5$. If the anti-hole in $G$ is of order $5$, then $C_5$ is an induced subgraph in the complement of $G$, but since $C_5=C_5^C$, $C_5$ is an induced subgraph in $G$. A contradiction.

Suppose, the odd anti-hole has order $2k+5,\ k \in \mathbb{N}$. It follows that the path $P_5$ of order $5$ is an induced subgraph in $G^C$, but $P_5^C$ is not chordal (it contains a $C_4$). A contradiction.