Every perfect graph is Berge
ProvedStrongPerfectGraph.Main.perfect_bergegraph-theoryperfect-graphs
Let be a finite simple graph. Call perfect if for every induced subgraph of , and Berge if every hole (induced cycle of length at least ) of and of its complement has even length. Then
This is the easy direction of the strong perfect graph theorem, recorded in the paper's introduction ("Since every perfect graph is Berge, to prove 1.2 it remains to prove the converse"). An odd hole , , has clique number but chromatic number ; an odd antihole is handled through Lovász's theorem 1.1 (the complement of a perfect graph is perfect).
Formalization Note Perfection and the Berge property are the mission definitions IsPerfect and IsBerge; holes are cyclically listed vertex lists (IsHole).
Preamble
import Mathlib import Definitions.Def_StrongPerfectGraph_Main_IsBerge import Definitions.Def_StrongPerfectGraph_Main_IsPerfect
Formal statement
namespace StrongPerfectGraph.Main
/-- Every perfect graph is Berge (the easy direction of Theorem 1.2, p. 52). -/
theorem perfect_berge {V : Type*} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) (hG : IsPerfect G) : IsBerge G := by sorry
end StrongPerfectGraph.Main
Source
Chudnovsky, Robertson, Seymour & Thomas, The strong perfect graph theorem, Ann. of Math. 164 (2006), 51-229, p. 52 (paragraph following Theorem 1.2: "every perfect graph is Berge")