Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 2 — an independent set RRR with G(R,V∖R)G(R,V\setminus R)G(R,V∖R) connected, alternating along a shortest path

Proved
OneTwoThree.Weighting.lemma_2

by mikedeng1 · Oct 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

1-2-3-conjecturegraph-theoryindependent-setp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Let G=(V,E)G=(V,E)G=(V,E) be a finite connected graph, let v,w∈Vv,w\in Vv,w∈V, and let p=(v1=v,v2,…,vk=w)p=(v_1=v,v_2,\dots,v_k=w)p=(v1​=v,v2​,…,vk​=w) be a shortest vvv-www-path in GGG. Then for each of the two choices "v∈Rv\in Rv∈R" and "v∉Rv\notin Rv∈/R" there exists an independent set R⊆VR\subseteq VR⊆V realizing that choice such that

  1. the bipartite graph G(R,V∖R)G(R,V\setminus R)G(R,V∖R), whose edges are the edges of GGG between RRR and V∖RV\setminus RV∖R, is connected, and
  2. the path ppp alternates between RRR and V∖RV\setminus RV∖R: for every i<ki<ki<k,
vi∈R  ⟺  vi+1∉R.v_i\in R\iff v_{i+1}\notin R.vi​∈R⟺vi+1​∈/R.

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 iii-th vertex is p.getVert i (indexed from 000). The choice of side for vvv is a Boolean b, quantified before the existential: for every b there is an R with v ∈ R ↔ b = true. Since R∪(V∖R)=VR\cup(V\setminus R)=VR∪(V∖R)=V, connectivity of G(R,V∖R)G(R,V\setminus R)G(R,V∖R) is connectivity of a graph on all of VVV.

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
  • Endorsed by Shuze Chen · Oct 9, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 9, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me