Proof of Corollary 5, p. 6 — the three inner vertices of a P₅
ProvedP7ThreeColor.Seed.p5_casedominating-setgraph-theoryinduced-pathp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a finite simple graph and let be a connected dominating set whose induced subgraph is isomorphic to the path . Then there is a connected set of exactly three vertices that 2-dominates :
This is the path case in the proof of Corollary 5.
Formalization Note Under the path isomorphism, is the image of the three non-leaf vertices. The Lean statement asserts the existence of such a set and carries the induced-subgraph isomorphism as a hypothesis.
Preamble
import Mathlib import Definitions.Def_P7ThreeColor_Seed_Basic
Formal statement
namespace P7ThreeColor.Seed
/-- Proof of Corollary 5, p. 6: the inner vertices of an induced `P₅` work. -/
theorem p5_case {V : Type*} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) (S : Finset V)
(hS : IsDominating G S) (hSconn : (G.induce (S : Set V)).Connected)
(e : G.induce (S : Set V) ≃g SimpleGraph.pathGraph 5) :
∃ T : Finset V, T.card = 3 ∧ T ⊆ S ∧
(G.induce (T : Set V)).Connected ∧ IsTwoDominating G T := 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, P₅ case
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.