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'.
Tony Huynh
- 32.1k
- 11
- 112
- 187