Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 8 v₀-extension — the ω₃ v₀-edge weighting + conflict-repair step

Open
OneTwoThree.Weighting.lemma_8_v0_extension

by junyihjy · Oct 11, 2026 · Mathlib 0df444a (Lean v4.33.1)

conflict-repairlemma-8one-two-threesource-faithful-childv0-extension

The v₀-extension step of Keusch's Lemma 8 (A Solution to the 1-2-3 Conjecture, arXiv:2303.02611v4, proof pp. 8–9).

Lemma 8's proof does NOT apply Lemma 7 to G[V∖{v₀}]. It re-runs the engine with v₀-aware inputs — Lemma 3 on G[B] with h(v) := 2|N(v)∖B|, Lemma 5 on the bipartite graph G(R,B) with R' := N(v₀)∩R and the two α-cases on N(v₀)∩B — and then extends the weighting to the v₀-incident edges in two elementary moves. This node isolates those two moves.

Hypotheses: the engine output on G[V∖{v₀}], formalized on G₀ := G.deleteIncidenceSet v₀ (SimpleGraph.deleteIncidenceSet: G with v₀'s incident edges removed — same edge set as the induced subgraph G[V∖{v₀}], vertex type V, so no subtype coercions): a {1,2,3}-weighting ω₁₂; designated odd colors f on B, pairwise distinct on B-neighbors; s_{ω₁₂} even on R exactly off N(v₀) (Lemma 5 (i)(ii) with R' = N(v₀)∩R); compensation weights c(v) ∈ {1,2,3} with s_{ω₁₂}(v) + c(v) = f(v) on N(v₀)∩B (and s_{ω₁₂} = f on B∖N(v₀)); and |N(v₀)∩R| + Σ_{v ∈ N(v₀)∩B} c(v) even — this evenness is what hpar buys in the paper (|N_R| even with all compensations 2, or |N_R| odd with one blue neighbor carrying an odd compensation in {1,3}). Plus lemma_8's own h2 (2 ≤ |N(v₀)∩R|), hpar, the good partition, and G[V∖{v₀}] connected.

Conclusion: a vertex-coloring {1,2,3}-weighting of G — lemma_8's conclusion (parent node OneTwoThree.Weighting.lemma_8, aaddfc19-dcf0-41a8-8dcd-fd1d40e9970f).

Proof idea (the paper's, pp. 8–9): (ω₃) put weight 1 on the v₀–R edges and c(v) on the v₀–B edges. Then s(v₀) is even by the evenness hypothesis; every red vertex is even again (odd + 1 on N(v₀)∩R, even elsewhere); every blue vertex attains its designated color f(v); since R is independent and f is odd/neighbor-distinct, the only possible coloring conflicts are between v₀ and its red neighbors. (Repair) write N(v₀)∩R = {v₁,…,v_k} with k ≥ 2 ordered by weighted degree; let x > 0 be smallest with s(v₀)+2x avoiding all s(vᵢ); raise selected v₀–R edge weights 1→3 (the paper's three cases on the position index) to get ω′ with s(v₀) distinct from every s(vᵢ) and no new conflicts. Finite parity/coloring case analysis on the edges v₀–N(v₀); no flow machinery. Sibling: lemma_7_from_lemma5 (6655c4ee-995d-496f-b728-21006c8f4542); lemma_5_path refinement d6776149-ae19-44e2-95f8-b7665a7474ce.

Preamble
import Mathlib
import Definitions.Def_OneTwoThree_Weighting_Setting
Formal statement
namespace OneTwoThree.Weighting

/-- Lemma 8 v₀-extension (Keusch, arXiv:2303.02611v4, Lemma 8 proof, pp. 8–9).

The paper proves Lemma 8 by re-running the engine on `G[V ∖ {v₀}]` (Lemma 3 on
`G[B]` with `h(v) := 2|N(v) ∖ B|`, Lemma 5 on `G(R,B)` with `R' := N(v₀) ∩ R`
and the two `α`-cases on `N(v₀) ∩ B`) and then extending the weighting to the
`v₀`-incident edges. This node is that extension step: `ω₃` (weight `1` on the
`v₀`–`R` edges, compensation weights `c` on the `v₀`–`B` edges, making `s(v₀)`
even) followed by the conflict repair (order `N(v₀) ∩ R` by weighted degree,
raise selected `v₀`–`R` edge weights `1 → 3` in the paper's three cases).
`G.deleteIncidenceSet v₀` is the edge-deletion form of `G[V ∖ {v₀}]` (same edge
set, vertex type `V`). -/
theorem lemma_8_v0_extension {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)
    [DecidableRel G.Adj] (v₀ : V) (hconn : (G.induce ({v₀}ᶜ : Set V)).Connected)
    (R B : Finset V) (hRB : IsGoodPartition G {v₀}ᶜ R B)
    (hengine : ∃ ω₁₂ : Sym2 V → ℕ, ∃ f : V → ℕ, ∃ c : V → ℕ,
      IsWeighting (G.deleteIncidenceSet v₀) 3 ω₁₂ ∧
      (∀ v ∈ B, Odd (f v)) ∧
      (∀ u v, u ∈ B → v ∈ B → (G.deleteIncidenceSet v₀).Adj u v → f u ≠ f v) ∧
      (∀ v ∈ R, Even (wdeg (G.deleteIncidenceSet v₀) ω₁₂ v) ↔ v ∉ G.neighborFinset v₀) ∧
      (∀ v ∈ B, v ∉ G.neighborFinset v₀ → wdeg (G.deleteIncidenceSet v₀) ω₁₂ v = f v) ∧
      (∀ v ∈ B, v ∈ G.neighborFinset v₀ →
        c v ∈ Finset.Icc 1 3 ∧ wdeg (G.deleteIncidenceSet v₀) ω₁₂ v + c v = f v) ∧
      Even (Finset.card (G.neighborFinset v₀ ∩ R) +
        Finset.sum (G.neighborFinset v₀ ∩ B) fun v => c v))
    (h2 : 2 ≤ Finset.card (G.neighborFinset v₀ ∩ R))
    (hpar : Even (Finset.card (G.neighborFinset v₀ ∩ R)) ∨
      1 ≤ Finset.card (G.neighborFinset v₀ ∩ B)) :
    ∃ ω : Sym2 V → ℕ, IsWeighting G 3 ω ∧ IsVertexColoring G ω := by sorry

end OneTwoThree.Weighting
Source
Keusch, A Solution to the 1-2-3 Conjecture, arXiv:2303.02611v4, Lemma 8 proof pp. 8-9 (v0-extension: ω3 construction + conflict repair)

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