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](http://diestel-graph-theory.com/).  It is Theorem 5.5, and afterwards includes a nice explanation by Diestel why the proof is 'natural'.