Id: palomar/PALOMAR-2026-11-06-000006 Url: https://github.com/mahdi-jfri/StrongPerfectGraphTheorem/tree/f81220fa3d8ebf987d44ab452f3abadb13c0ac2d Json: https://data.palomar-registry.org/entries/PALOMAR-2026-11-06-000006-v1.json Repo: https://github.com/mahdi-jfri/StrongPerfectGraphTheorem Tags: math.CO, cs.DM, msc:05C17, msc:05C75, msc:05C15, msc:05C69, msc:05C76 Score: 0 Title: The Strong Perfect Graph Theorem Trust: high Domain: math.CO Source: palomar Authors: Arshia Soltani Moakhar, Iman Gholami, Max Springer, Mahdi JafariRaviz, MohammadTaghi Hajiaghayi Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Verified: true Discussed: 0 Published: 2026-11-06 Formalized: true Formalizes: title=The strong perfect graph theorem identifier=doi:10.4007/annals.2006.164.51 relationship=formalizes Page: https://delphi.science/r/palomar/PALOMAR-2026-11-06-000006 A Lean 4 proof of the Strong Perfect Graph Theorem of Chudnovsky, Robertson, Seymour and Thomas: a finite graph is perfect if and only if it is Berge. A graph is perfect if every induced subgraph has chromatic number equal to its clique number. It is Berge if neither the graph nor its complement contains an induced cycle of odd length at least five. The proof follows the paper of Chudnovsky, Robertson, Seymour and Thomas (Annals of Mathematics, 2006). It formalizes the decomposition theorem for Berge graphs (Theorem 1.3 of the paper) through the numbered results of Sections 2 to 24. It also…