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