Lemma 2 — an independent set with connected, alternating along a shortest path
ProvedOneTwoThree.Weighting.lemma_21-2-3-conjecturegraph-theoryindependent-setp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a finite connected graph, let , and let be a shortest --path in . Then for each of the two choices "" and "" there exists an independent set realizing that choice such that
- the bipartite graph , whose edges are the edges of between and , is connected, and
- the path alternates between and : for every ,
The lemma supplies the red/blue vertex partition on which the whole construction is built.
Formalization Note The path is a walk p : G.Walk v w whose length equals the graph distance (which makes it a path). Its -th vertex is p.getVert i (indexed from ). The choice of side for is a Boolean b, quantified before the existential: for every b there is an R with v ∈ R ↔ b = true. Since , connectivity of is connectivity of a graph on all of .
Preamble
import Mathlib import Definitions.Def_OneTwoThree_Weighting_Setting
Formal statement
namespace OneTwoThree.Weighting
open Finset SimpleGraph
theorem lemma_2 {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)
(hG : G.Connected) {v w : V} (p : G.Walk v w) (hp : p.length = G.dist v w) (b : Bool) :
∃ R : Finset V, G.IsIndepSet (R : Set V) ∧
(G.between (R : Set V) (R : Set V)ᶜ).Connected ∧
(∀ i < p.length, (p.getVert i ∈ R ↔ p.getVert (i + 1) ∉ R)) ∧
(v ∈ R ↔ b = true) := by sorry
end OneTwoThree.Weighting
Source
Keusch, A Solution to the 1-2-3 Conjecture, arXiv:2303.02611v4, p. 3, Lemma 2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.