§3.1, p. 15 — no vertex of X has a neighbor in S
ProvedP7ThreeColor.Lemma11.X_no_nbr_in_Sgraph-theorylist-coloringp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1p7-free
Let , and satisfy the hypotheses of Lemma 11, and let be the set of vertices with . Then
Together with the anticompleteness hypothesis of Lemma 11, this confines the neighborhood of each to , and since is stable, to .
Preamble
import Mathlib import Definitions.Def_P7ThreeColor_Lemma11_Setting
Formal statement
namespace P7ThreeColor.Lemma11
/-- p. 15: under the hypothesis of Lemma 11, no vertex of `X` has a neighbor in `S`. -/
theorem X_no_nbr_in_S {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)
(L : V → Finset (Fin 3)) (S : Finset V) (hyp : Lemma11Hyp G L S)
(x s : V) (hx : x ∈ X L) (hs : s ∈ S) :
¬ G.Adj x s := by sorry
end P7ThreeColor.Lemma11
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. 15, §3.1, second paragraph ("By the same hypothesis, no vertex of X has neighbors in S.")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.