Proof of Corollary 5, p. 6 — a connected P₃-free graph is complete
ProvedP7ThreeColor.Seed.connected_p3free_completegraph-theoryinduced-pathp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1p3-free
Let be a connected simple graph with no induced path on three vertices. Every two distinct vertices of are adjacent:
This is the completeness observation used in the final case of Corollary 5.
Formalization Note No finiteness assumption is required for this observation. Connectedness includes a nonempty vertex set.
Preamble
import Mathlib import Definitions.Def_P7ThreeColor_Seed_Basic
Formal statement
namespace P7ThreeColor.Seed
/-- Proof of Corollary 5, p. 6: a connected `P₃`-free graph is complete. -/
theorem connected_p3free_complete {W : Type*} (H : SimpleGraph W)
(hH : H.Connected) (h3 : PFree 3 H) :
∀ u v : W, u ≠ v → H.Adj u v := by sorry
end P7ThreeColor.Seed
Source
Bonomo, Chudnovsky, Maceli, Schaudt, Stein and Zhong, Three-coloring and list three-coloring of graphs without induced paths on seven vertices, Combinatorica (2017), DOI 10.1007/s00493-017-3553-8, p. 6, proof of Corollary 5, final sentence
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.