A minimum imperfect graph admits no proper homogeneous pair
OpenStrongPerfectGraph.Main.minimum_imperfect_no_proper_homogeneous_pairLet be a minimum imperfect graph: a Berge graph that is not perfect, such that every Berge graph with fewer vertices is perfect. Then admits no proper homogeneous pair:
Here a proper homogeneous pair is a pair of disjoint nonempty vertex sets such that, writing for the sets of -complete and -anticomplete vertices and similarly, we have and the four sets , , , are all nonempty.
The paper attributes this to Chvátal and Sbihi (reference [7], Bull-free Berge graphs are perfect, Graphs Combin. 3 (1987), 127–139) in the proof of 1.2 assuming 1.3: "It is shown in [7] that G does not admit a proper homogeneous pair." 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 IsProperHomogeneousPair are the mission definitions.
import Mathlib import Definitions.Def_StrongPerfectGraph_Main_IsMinimumImperfect import Definitions.Def_StrongPerfectGraph_Main_IsProperHomogeneousPair
namespace StrongPerfectGraph.Main
/-- Chvátal–Sbihi: a minimum imperfect graph admits no proper homogeneous pair (p. 56). -/
theorem minimum_imperfect_no_proper_homogeneous_pair {V : Type*} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) (hG : IsMinimumImperfect G) : ¬ IsProperHomogeneousPair G := by sorry
end StrongPerfectGraph.Main