# Why is the Petersen graph not a perfect graph?

As I understand, 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. Should I show, that chromatic numbers of all Petersen's subgraphs are not equal to it clique number? Maybe there is an easier and quickly way to show that.

## 2 Answers

The Petersen graph is a Kneser graph, precisely $\text{KG}(5,2)$. By Lovasz theorem the chromatic number of $\text{KG}(n,k)$ is $n-2k+2$, hence in our case $\chi(G)=3$. On the other hand $5<6$, hence the Petersen graph is triangle-free.

• Is there any theorem, that perfect graph can't be triangle-free? – Rijndael Feb 1 '17 at 20:32
• Using the Lovasz theorem on Kneser graphs seems like major overkill. The Peterson graph contains an induced pentagon, qed. – Nate Feb 1 '17 at 20:32
• @Nate: I agree with you. I was just in the mood of killing mosquitoes with atomic bombs. – Jack D'Aurizio Feb 1 '17 at 20:52

Check out this link --- it shows the clique number is less than the chromatic number of the entire graph.

http://mathworld.wolfram.com/PetersenGraph.html

• Thanks, I saw it. But, I didn't clearly understand where the proof, that the clique number is less – Rijndael Feb 1 '17 at 20:29