1.1 — complement of a perfect graph
ProvedStrongPerfectGraph.Main.complement_perfectgraph-theoryp2o-batch-pfp1bp2o-gran-per-chapterp2o-plan-bookp2o-v1perfect-graphs
Let be a finite simple graph. If is perfect, then its complement is perfect:
Perfection means equality of chromatic and clique numbers for every induced subgraph. This is Lovász’s theorem, stated as 1.1 and used in the reduction from 1.3 to the strong perfect graph theorem.
Preamble
import Mathlib import Definitions.Def_StrongPerfectGraph_Main_IsPerfect
Formal statement
namespace StrongPerfectGraph.Main
/-- Lovász's theorem, cited as Theorem 1.1. -/
theorem complement_perfect {V : Type*} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) (hG : IsPerfect G) : IsPerfect Gᶜ := by sorry
end StrongPerfectGraph.Main
Source
Chudnovsky, Robertson, Seymour & Thomas, The strong perfect graph theorem, Ann. of Math. 164 (2006), p. 52, 1.1, cited from Lovász [16]
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.