Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
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

2 Answers 2

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'.

share|improve this answer
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

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

share|improve this answer
The link is broken now. –  Petr Hudeček Feb 3 at 13:09
Thanks Petr, updated the link. –  Andrew D. King Feb 6 at 19:57

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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