proving that if graph has perfect elimination order than the graph is perfect I need help with this problem:
Let say that G has a perfect elimination order, than I have to prove that G is perfect.
Can someone help me with that?
I've tried to solve it with induction but I did not succeed..
Here's a route you can take.
Prove (or use the fact) that a graph is chordal iff it has a perfect elimination order. Now, it will suffice to show that a chordal graph is perfect. For that, you can take the strong perfect graph theorem stating that a graph is perfect iff it contains no odd hole and no odd antihole. Proceed by contradiction.