Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

All basic graphs are perfect

Proved
StrongPerfectGraph.Main.basic_perfect

by tianyipeng · Nov 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

graph-theoryperfect-graphs

Let GGG be a finite simple graph. Following the paper, GGG is basic if one of the following holds:

  1. GGG is bipartite;
  2. G‾\overline GG is bipartite;
  3. GGG is isomorphic to the line graph L(H)L(H)L(H) of a bipartite graph HHH;
  4. G‾\overline GG is isomorphic to the line graph of a bipartite graph;
  5. GGG is a double split graph.

Then every basic graph is perfect:

G basic ⟹ χ(G∣X)=ω(G∣X)  for all X⊆V(G).G\ \text{basic}\ \Longrightarrow\ \chi(G|X)=\omega(G|X)\ \text{ for all } X\subseteq V(G).G basic ⟹ χ(G∣X)=ω(G∣X)  for all X⊆V(G).

The paper states "It is easy to see that all basic graphs are perfect": for bipartite graphs this is trivial; for line graphs of bipartite graphs it is König's edge-colouring theorem; for their complements it follows from Lovász's theorem 1.1; and for double split graphs it is left to the reader. It is one of the ingredients of the derivation of Theorem 1.2 from the decomposition theorem 1.3.

Formalization Note IsBasic is the mission definition; line graphs are taken of a graph on Fin n, up to graph isomorphism.

Preamble
import Mathlib
import Definitions.Def_StrongPerfectGraph_Main_IsBasic
import Definitions.Def_StrongPerfectGraph_Main_IsPerfect
Formal statement
namespace StrongPerfectGraph.Main

/-- Every basic graph is perfect (p. 53). -/
theorem basic_perfect {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) (hG : IsBasic G) : IsPerfect G := by sorry

end StrongPerfectGraph.Main
Source
Chudnovsky, Robertson, Seymour & Thomas, The strong perfect graph theorem, Ann. of Math. 164 (2006), 51-229, p. 53 (sentence "It is easy to see that all basic graphs are perfect", after the definition of basic graphs)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me