A minimum imperfect graph admits no proper 2-join
OpenStrongPerfectGraph.Main.minimum_imperfect_no_proper_two_joinCall a finite graph a minimum imperfect graph if it is Berge, not perfect, and every Berge graph with fewer vertices than is perfect (i.e. is a counterexample to the strong perfect graph theorem with as few vertices as possible). Then admits no proper 2-join:
Here a proper 2-join is a partition of with disjoint nonempty such that is complete to , is complete to , there are no other edges between and , every component of meets both and , and if and is a path joining them then that path has odd length at least .
The paper attributes this to Cornuéjols and Cunningham (reference [13], Compositions for perfect graphs, Discrete Math. 55 (1985), 245–254) in the proof of 1.2 assuming 1.3: "It is shown in [13] that G does not admit a proper 2-join." It is one of the ingredients used to rule out every outcome of the decomposition theorem 1.3 for a minimum imperfect graph.
Formalization Note IsMinimumImperfect and IsProperTwoJoin are the mission definitions; minimality quantifies over all Berge graphs on Fin n with n smaller than the number of vertices of .
import Mathlib import Definitions.Def_StrongPerfectGraph_Main_IsMinimumImperfect import Definitions.Def_StrongPerfectGraph_Main_IsProperTwoJoin
namespace StrongPerfectGraph.Main
/-- Cornuéjols–Cunningham: a minimum imperfect graph admits no proper 2-join (p. 56). -/
theorem minimum_imperfect_no_proper_two_join {V : Type*} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) (hG : IsMinimumImperfect G) : ¬ IsProperTwoJoin G := by sorry
end StrongPerfectGraph.Main