Lemma 5 (i)–(iii) — a bipartite -weighting with prescribed parities on and on
ProvedOneTwoThree.Weighting.lemma_51-2-3-conjecturebipartite-graphedge-weightinggraph-labellingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a finite connected bipartite graph with parts and (every edge joins to ). Let satisfy
and let be such that is even. Then there exists an edge-weighting such that
- is even for all ,
- is odd for all , and
- for all .
The lemma weights the red-blue edges: blue vertices receive exactly the missing amount and red vertices receive prescribed parities.
Formalization Note is the complement of and bipartiteness is the condition that every edge has exactly one end in . is typed , but only its values on occur. The membership is stated in , so no truncated subtraction appears; is the degree in .
Preamble
import Mathlib import Definitions.Def_OneTwoThree_Weighting_Setting
Formal statement
namespace OneTwoThree.Weighting
open Finset SimpleGraph
theorem lemma_5 {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)
[DecidableRel G.Adj] (hG : G.Connected) (B : Finset V)
(hB : ∀ u v, G.Adj u v → (u ∈ B ↔ v ∉ B)) (α : V → ℕ)
(hα : ∀ v ∈ B, (α v : ℤ) = 2 * (G.degree v : ℤ) - 1 ∨ (α v : ℤ) = 2 * (G.degree v : ℤ) ∨
(α v : ℤ) = 2 * (G.degree v : ℤ) + 1)
(R' : Finset V) (hR' : R' ⊆ Bᶜ) (hpar : Even (#R' + ∑ v ∈ B, α v)) :
∃ ω : Sym2 V → ℕ, IsWeighting G 3 ω ∧
(∀ v ∈ Bᶜ \ R', Even (wdeg G ω v)) ∧
(∀ v ∈ R', Odd (wdeg G ω v)) ∧
(∀ v ∈ B, wdeg G ω v = α v) := by sorry
end OneTwoThree.Weighting
Source
Keusch, A Solution to the 1-2-3 Conjecture, arXiv:2303.02611v4, p. 6, Lemma 5 (i)–(iii)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.