Editing Strong perfect graph theorem (section)

==Proof ideas==
The proof of the strong perfect graph theorem by Chudnovsky et al. follows an outline conjectured in 2001 by Conforti, Cornuéjols, Robertson, Seymour, and Thomas, according to which every Berge graph either forms one of five types of basic building block (special classes of perfect graphs) or it has one of four different types of structural decomposition into simpler graphs. A minimally imperfect Berge graph cannot have any of these decompositions, from which it follows that no [[counterexample]] to the theorem can exist.<ref>{{harvtxt|Cornuéjols|2002}}, Conjecture 5.1.</ref> This idea was based on previous conjectured structural decompositions of similar type that would have implied the strong perfect graph conjecture but turned out to be false.<ref>{{harvtxt|Reed|1986}}; {{harvtxt|Hougardy|1991}}; {{harvtxt|Rusu|1997}}; {{harvtxt|Roussel|Rusu|Thuillier|2009}}, section 4.6 "The first conjectures".</ref>

The five basic classes of perfect graphs that form the base case of this structural decomposition are the bipartite graphs, [[line graph]]s of bipartite graphs, [[complement graph|complementary graph]]s of bipartite graphs, complements of line graphs of bipartite graphs, and double split graphs. It is easy to see that bipartite graphs are perfect: in any nontrivial induced subgraph, the clique number and chromatic number are both two and therefore are equal. The perfection of complements of bipartite graphs, and of complements of line graphs of bipartite graphs, are both equivalent to [[Kőnig's theorem (graph theory)|Kőnig's theorem]] relating the sizes of [[maximum matching]]s, [[maximum independent set]]s, and [[vertex cover problem|minimum vertex covers]] in bipartite graphs. The perfection of line graphs of bipartite graphs can be stated equivalently as the fact that bipartite graphs have [[chromatic index]] equal to their maximum [[degree (graph theory)|degree]], proven by {{harvtxt|Kőnig|1916}}. Thus, all four of these basic classes are perfect. The double split graphs are a relative of the [[split graph]]s that can also be shown to be perfect.<ref>{{harvtxt|Roussel|Rusu|Thuillier|2009}}, Definition 4.39.</ref>

The four types of decompositions considered in this proof are 2-joins, complements of 2-joins, balanced skew partitions, and homogeneous pairs.

A 2-join is a partition of the vertices of a graph into two subsets, with the property that the edges spanning the cut between these two subsets form two vertex-disjoint [[complete bipartite graph]]s. When a graph has a 2-join, it may be decomposed into induced subgraphs called "blocks", by replacing one of the two subsets of vertices by a shortest path within that subset that connects one of the two complete bipartite graphs to the other; when no such path exists, the block is formed instead by replacing one of the two subsets of vertices by two vertices, one for each complete bipartite subgraph. A 2-join is perfect if and only if its two blocks are both perfect. Therefore, if a minimally imperfect graph has a 2-join, it must equal one of its blocks, from which it follows that it must be an odd cycle and not Berge. For the same reason, a minimally imperfect graph whose complement has a 2-join cannot be Berge.<ref>{{harvtxt|Cornuéjols|Cunningham|1985}}; {{harvtxt|Cornuéjols|2002}}, Theorem 3.2 and Corollary 3.3.</ref>

A [[skew partition]] is a partition of a graph's vertices into two subsets, one of which induces a disconnected subgraph and the other of which has a disconnected complement; {{harvtxt|Chvátal|1985}} had conjectured that no minimal counterexample to the strong perfect graph conjecture could have a skew partition. Chudnovsky et al. introduced some technical constraints on skew partitions, and were able to show that Chvátal's conjecture is true for the resulting "balanced skew partitions". The full conjecture is a corollary of the strong perfect graph theorem.<ref>{{harvtxt|Seymour|2006}}; {{harvtxt|Roussel|Rusu|Thuillier|2009}}, section 4.7 "The skew partition"; {{harvtxt|Cornuéjols|2002}}, Theorems 4.1 and 4.2.</ref>

A homogeneous pair is related to a [[modular decomposition]] of a graph. It is a partition of the graph into three subsets ''V''<sub>1</sub>, ''V''<sub>2</sub>, and ''V''<sub>3</sub> such that ''V''<sub>1</sub> and ''V''<sub>2</sub> together contain at least three vertices, ''V''<sub>3</sub> contains at least two vertices, and for each vertex ''v'' in  ''V''<sub>3</sub> and each ''i'' in {1,2} either ''v'' is adjacent to all vertices in ''V<sub>i</sub>'' or to none of them. It is not possible for a minimally imperfect graph to have a homogeneous pair.<ref>{{harvtxt|Chvátal|Sbihi|1987}}; {{harvtxt|Cornuéjols|2002}}, Theorem 4.10.</ref> Subsequent to the proof of the strong perfect graph conjecture, {{harvtxt|Chudnovsky|2006}} simplified it by showing that homogeneous pairs could be eliminated from the set of decompositions used in the proof.

The proof that every Berge graph falls into one of the five basic classes or has one of the four types of decomposition follows a case analysis, according to whether certain configurations exist within the graph: a "stretcher", a subgraph that can be decomposed into three induced paths subject to certain additional constraints, the complement of a stretcher, and a "proper wheel", a configuration related to a [[wheel graph]], consisting of an induced cycle together with a hub vertex adjacent to at least three cycle vertices and obeying several additional constraints. For each possible choice of whether a stretcher or its complement or a proper wheel exists within the given Berge graph, the graph can be shown to be in one of the basic classes or to be decomposable.<ref>{{harvtxt|Cornuéjols|2002}}, Theorems 5.4, 5.5, and 5.6; {{harvtxt|Roussel|Rusu|Thuillier|2009}}, Theorem 4.42.</ref> This case analysis completes the proof.