I recently came across a family of infinite graphs (in the context of two-dimensional convexity) that don't have induced 4-paths (paths with 4 vertices). 
Note that the complement of a 4-path is again a 4-path.  

Clearly, every induced $n+1$-cycle contains an induced $n$-path.  

Hence, by the Strong Perfect Graph Theorem of Chudnowski, Robertson, Seymour, and Thomas,
graphs without induced 4-paths are perfect. 


Can anyone provide a simple proof of that fact?  

Having no induced 4-paths seems like a very strong condition.



Simple proof that these graphs are perfect
These P4-free graphs are also known as [cographs](http://en.wikipedia.org/wiki/Cograph). A simple proof of the perfectness of such graphs was given by Seinsche, *On a property of the class of n-colorable graphs*, J. Comb. Th. Ser. B 16 (1974), 191–193. [MR0337679](http://www.ams.org/mathscinet-getitem?mr=337679) The key to the proof is the fact that these graphs are also characterized by the property that every subset of $V(G)$ with more than one element is either not $G$-connected or not $\overline{G}$-connected. It follows that every such graph can be obtained from a single vertex by repeatedly duplicating vertices with or without an edge between the two duplicates. Since these two duplication operations preserve perfectness, all such graphs are perfect. (This quick argument is due to Lovász.)


