# Proving perfect graph has no odd cycles of length greater than three

In my studies of graph theory I recently came across the following interesting question that got me stuck, but first a definition:

A perfect graph is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph.

The question involved here is:

Let G be a finite and simple undirected graph which is perfect (all subgraphs of it are perfect) and we are asked to prove G contains no odd cycle of length greater than three

To be quite honest, I cannot seem to relate the lack of odd cycles to the graph being perfect, so I have no idea on this here and I would certainly appreciate help on this.

The key is that odd cycles of length greater than three are not perfect, with the following proof :

First, let's show that these cycles have a chromatic number of $3$.

Assume we have colors $c_1$ and $c_2$, and we have a cycle of nodes $n_1, \dots, n_{2n+1}$. We assign $c_1$ to $n_1$ without loss of generality, and necessarily $n_2$ has color $c_2$, and by immediate recursion all $n_{2k}$ are of color $c_2$, and all $n_{2k+1}$ are of color $c_1$.

Especially, $n_1$ and $n_{2n+1}$ have the same color, but are connected: contradiction.

Now, we deduce from it that they are not perfect.

In odd cycles of size greater than three the largest clique is of size $2$, but as seen before their chromatic number is $3$. So odd cycles of length greater than three are not perfect.

(Note that in a cycle of $3$ elements, the largest clique is of size $3$, hence the necessary lower bound on the size of the cycle.)

Having this said, let us suppose that the perfect graph $G$ contains an odd cycle $C$ of length greater than 3. Then $C$ is an induced subgraph of $G$ and as such, should be perfect. Contradiction.