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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.