The Strong Perfect Graph Theorem
Source: github.com/mahdi-jfri/StrongPerfectGraphTheorem/tree/f81220…
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/palomar/PALOMAR-2026-11-06-000006
curl -X POST /api/v1/records/palomar/PALOMAR-2026-11-06-000006/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/palomar/PALOMAR-2026-11-06-000006/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'