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

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

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

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