# Combinatorial Proof of Weak Perfect Graph Theorem.

I am reading Andras Frank's Connections in Combinatorial Optimization. On the Page 34, the description of how to use the Replication Lemma to prove the weak perfect graph theorem seems only to prove that there must be a largest maximal stable set intersecting all largest cliques, if not, a contradiction occur. I think that there are some more steps are needed.

I have understood the proof in Frank's Connections in Combinatorial Optimization.It is interesting that how natural about the combinatorial proof.

-
So ist your question wether you are right or not, or what the missing steps are? Perhaps you could explain a bit, why you think that the proof is insufficient. – Abel Stolz May 26 '11 at 9:27
Hi, Abel. Do you know how to use the relication lemma to prove the weak perfect graph theorem? – Haoran Wang May 27 '11 at 1:00
I have understood that the Description by Andras Frank. – Haoran Wang Jun 20 '11 at 4:11

I feel a bit guilty because this is the second time I have pointed someone to my thesis for fundamental material, but the proof of the WPGT via the Replication Lemma is in Section 3.2. http://www.sfu.ca/~adk7/papers/phdthesis-compact.pdf

-
The link is broken now. – Petr Hudeček Feb 3 '14 at 13:09
Thanks Petr, updated the link. – Andrew D. King Feb 6 '14 at 19:57

Lovász' original 1972 proof of the (weak) perfect graph theorem was completely combinatorial. The proof can be found in Diestel's book Graph Theory, which you can peruse for free online here. It is Theorem 5.5.4, and afterwards includes a nice explanation by Diestel why vertex replication is 'natural'.

-
Thanks a lot for that! – Haoran Wang Jun 18 '11 at 2:17
You're welcome. If you feel that this answers your question, then you can click on the green checkmark to indicate so. – Tony Huynh Jun 20 '11 at 10:10
I will do that. In fact, I feel that the explanation by Andras Frank in his book is really really good and elegant. I am shame to say that just at first glance, I did not understood a key point. – Haoran Wang Jun 21 '11 at 1:48