Corollary 5, p. 6 — a small connected 2-dominating set or a K₄
ProvedP7ThreeColor.Seed.corollary_5dominating-setgraph-theoryinduced-pathp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1p7-free
Let be a finite connected simple graph with no induced path on seven vertices. Then has a connected 2-dominating set of at most three vertices or contains a complete subgraph on four vertices:
The result supplies a small structural seed for the paper's graph-coloring analysis whenever the obstruction is absent.
Formalization Note The paper's second sentence, which gives a running time for finding the set or subgraph, is outside this statement because no machine model is part of the mission. A complete subgraph of four vertices is represented by ¬ G.CliqueFree 4; the disjunction is inclusive.
Preamble
import Mathlib import Definitions.Def_P7ThreeColor_Seed_Basic
Formal statement
namespace P7ThreeColor.Seed
/-- First statement of Corollary 5, p. 6. -/
theorem corollary_5 {V : Type*} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) (hG : G.Connected) (h7 : PFree 7 G) :
(∃ S : Finset V, S.card ≤ 3 ∧ (G.induce (S : Set V)).Connected ∧
IsTwoDominating G S) ∨ ¬ G.CliqueFree 4 := 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, Corollary 5, first sentence
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.