cut_layer_potential_lipschitz
The 4-layer potential satisfies f a - f b ≤ dist(a, b) for all vertices a, b.
Statement
theorem cut_layer_potential_lipschitz {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) (X : Finset V) (a b : V) : cut_layer_potential G X a - cut_layer_potential G X b ≤ (G.dist a b : ℝ)
- Source
- step towards exists_dist_three_cut_potential_witness
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- cut_layer_potentialThe 4-layer potential takes value 0 on vertices of X with no neighbors in Xᶜ, 1 on vertices of X with a neighbor in Xᶜ, 2 on vertices of…
The proof, explained
The 4-layer potential partitions the graph into four layers taking values 0, 1, 2, and 3 depending on whether a vertex is in the interior or boundary of X or of its complement Xᶜ. A case analysis on whether adjacent vertices belong to X shows that the potential changes by at most 1 across any edge. By induction on walks, the difference in potential between any two vertices is bounded by the length of any walk connecting them. On a connected graph, evaluating this bound on a walk of minimum length shows the potential difference is bounded by the graph distance, proving that the potential is 1-Lipschitz.
The potential is non-negative at every vertex: 0 ≤ cut_layer_potential G X v.
Unfolding the definition of cut_layer_potential gives four possible values ({0, 1, 2, 3}) according to membership in X and the existence of cut-crossing edges. Case splitting across all branches with split_ifs followed by norm_num verifies that every case is non-negative.
unfold cut_layer_potential split_ifs <;> norm_num
The potential is at most 3 at every vertex: cut_layer_potential G X v ≤ 3.
Unfolding the definition and splitting across all conditional branches, norm_num verifies that each branch value is at most 3.
unfold cut_layer_potential split_ifs <;> norm_num
If v ∈ X, the potential is at most 1: cut_layer_potential G X v ≤ 1.
Unfolding the definition and using the hypothesis v ∈ X simplifies the outer conditional via if_pos to an expression taking values 1 or 0, both of which norm_num verifies are at most 1.
uses
if_posunfold cut_layer_potential rw [if_pos hv] split_ifs <;> norm_num
If v ∉ X, the potential is at least 2: 2 ≤ cut_layer_potential G X v.
Unfolding the definition and using v ∉ X reduces the outer conditional via if_neg to an expression taking values 2 or 3, both of which are at least 2.
uses
if_negunfold cut_layer_potential rw [if_neg hv] split_ifs <;> norm_num
If v ∉ X has a neighbor in X, its potential is exactly 2: cut_layer_potential G X v = 2.
Unfolding the definition, the hypothesis v ∉ X selects the outer else-branch via if_neg, and the existence of a neighbor in X selects 2 via if_pos.
uses
if_neg,if_posunfold cut_layer_potential rw [if_neg hv, if_pos h]
If v ∈ X has a neighbor outside X, its potential is exactly 1: cut_layer_potential G X v = 1.
Unfolding the definition, the hypothesis v ∈ X selects the then-branch via if_pos, and the existence of a neighbor in the complement Xᶜ selects 1 via if_pos.
uses
if_posunfold cut_layer_potential rw [if_pos hv, if_pos h]
If u ∈ X and G.Adj u v, then cut_layer_potential G X u - cut_layer_potential G X v ≤ 1.
We split on whether v ∈ X. If v ∈ X, then f(u) ≤ 1 by cut_layer_potential_lipschitz_of_mem and f(v) ≥ 0 by cut_layer_potential_lipschitz_nonneg, so f(u) - f(v) ≤ 1 - 0 = 1. If v ∉ X, then v has neighbor u ∈ X by symmetry of adjacency, so f(v) = 2 by cut_layer_potential_lipschitz_eq_two; since f(u) ≤ 1, linear arithmetic gives f(u) - f(v) ≤ 1 - 2 ≤ 1.
uses
cut_layer_potential_lipschitz_of_mem,cut_layer_potential_lipschitz_nonneg,cut_layer_potential_lipschitz_eq_twoby_cases hu : u ∈ X · by_cases hv : v ∈ X · have := cut_layer_potential_lipschitz_of_mem G X hu have := cut_layer_potential_lipschitz_nonneg G X v linarith · have hfv := cut_layer_potential_lipschitz_eq_two G X hv ⟨u, hu, h.symm⟩ have := cut_layer_potential_lipschitz_of_mem G X hu linarith
If u ∉ X and G.Adj u v, then cut_layer_potential G X u - cut_layer_potential G X v ≤ 1.
We split on whether v ∈ X. If v ∈ X, then u ∈ Xᶜ (via Finset.mem_compl.mpr) is a neighbor of v outside X, so f(v) = 1 by cut_layer_potential_lipschitz_eq_one, while v ∈ X is a neighbor of u in X, so f(u) = 2 by cut_layer_potential_lipschitz_eq_two; thus f(u) - f(v) = 2 - 1 = 1. If v ∉ X, then f(u) ≤ 3 by cut_layer_potential_lipschitz_le_three and f(v) ≥ 2 by cut_layer_potential_lipschitz_of_not_mem, so f(u) - f(v) ≤ 3 - 2 = 1.
uses
cut_layer_potential_lipschitz_eq_two,cut_layer_potential_lipschitz_eq_one,Finset.mem_compl.mpr,cut_layer_potential_lipschitz_le_three,cut_layer_potential_lipschitz_of_not_mem· by_cases hv : v ∈ X · have hfu := cut_layer_potential_lipschitz_eq_two G X hu ⟨v, hv, h⟩ have hfv := cut_layer_potential_lipschitz_eq_one G X hv ⟨u, Finset.mem_compl.mpr hu, h.symm⟩ linarith · have := cut_layer_potential_lipschitz_le_three G X u have := cut_layer_potential_lipschitz_of_not_mem G X hv linarith
The potential difference along any walk p from u to v is at most its length: cut_layer_potential G X u - cut_layer_potential G X v ≤ p.length.
By induction on p. For a trivial walk (nil), length is 0 and the potential difference is 0, which simp closes. For a walk cons h q prepending edge h to walk q, its length is q.length + 1 by SimpleGraph.Walk.length_cons. The difference across h is at most 1 by cut_layer_potential_lipschitz_adj, and along q is at most q.length by the induction hypothesis; linarith sums these bounds.
uses
SimpleGraph.Walk.length_cons,cut_layer_potential_lipschitz_adjinduction p with | nil => simp | cons h q ih => rw [SimpleGraph.Walk.length_cons] push_cast have h1 := cut_layer_potential_lipschitz_adj G X h linarith
A geodesic walk between a and b bounds the potential difference by the graph distance: cut_layer_potential G X a - cut_layer_potential G X b ≤ dist(a, b).
Because G is connected, there exists a walk p from a to b whose length equals dist(a, b). Applying cut_layer_potential_lipschitz_walk to p bounds f(a) - f(b) by p.length, and rewriting with the length equality yields the distance bound.
uses
cut_layer_potential_lipschitz_walkobtain ⟨p, hp⟩ := hG.exists_walk_length_eq_dist a b have h := cut_layer_potential_lipschitz_walk G X p rw [hp] at h exact h
cut_layer_potential_lipschitz_nonneg- The cut layer potential is non-negative at every vertex: 0 ≤ cut_layer_potential G X v.
cut_layer_potential_lipschitz_le_three- The cut layer potential is at most 3 at every vertex: cut_layer_potential G X v ≤ 3.
cut_layer_potential_lipschitz_of_mem- A vertex belonging to X has cut layer potential at most 1: v ∈ X → cut_layer_potential G X v ≤ 1.
cut_layer_potential_lipschitz_of_not_mem- A vertex outside X has cut layer potential at least 2: v ∉ X → 2 ≤ cut_layer_potential G X v.
cut_layer_potential_lipschitz_eq_two- A vertex outside X with a neighbor in X has cut layer potential exactly 2: v ∉ X → (∃ w ∈ X, G.Adj v w) → cut_layer_potential G X v = 2.
cut_layer_potential_lipschitz_eq_one- A vertex in X with a neighbor outside X has cut layer potential exactly 1: v ∈ X → (∃ w ∈ Xᶜ, G.Adj v w) → cut_layer_potential G X v = 1.
cut_layer_potential_lipschitz_adj- Adjacent vertices have potential difference at most 1: G.Adj u v → cut_layer_potential G X u - cut_layer_potential G X v ≤ 1.
cut_layer_potential_lipschitz_walk- The potential difference between endpoints of any walk is bounded by the walk length: cut_layer_potential G X u - cut_layer_potential G X v ≤ p.length.
if_pos- If a condition holds, an if-then-else expression evaluates to its then branch.
if_neg- If a condition does not hold, an if-then-else expression evaluates to its else branch.
Finset.mem_compl.mpr- An element not belonging to a finite set belongs to its complement: a ∉ s → a ∈ sᶜ.
SimpleGraph.Walk.length_cons- The length of a walk with an edge prepended is one more than the length of the tail walk.
- The potential cut_layer_potential takes only four discrete values {0, 1, 2, 3} depending on whether a vertex is in the interior or boundary of X or Xᶜ. Lemmas cut_layer_potential_lipschitz_nonneg, cut_layer_potential_lipschitz_le_three, cut_layer_potential_lipschitz_of_mem, and cut_layer_potential_lipschitz_of_not_mem are all discharged by split_ifs and norm_num testing these four possible numerical assignments.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
lemma cut_layer_potential_lipschitz_nonneg {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (X : Finset V) (v : V) : 0 ≤ cut_layer_potential G X v := by unfold cut_layer_potential split_ifs <;> norm_numlemma cut_layer_potential_lipschitz_le_three {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (X : Finset V) (v : V) : cut_layer_potential G X v ≤ 3 := by unfold cut_layer_potential split_ifs <;> norm_numlemma cut_layer_potential_lipschitz_of_mem {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (X : Finset V) {v : V} (hv : v ∈ X) : cut_layer_potential G X v ≤ 1 := by unfold cut_layer_potential rw [if_pos hv] split_ifs <;> norm_numlemma cut_layer_potential_lipschitz_of_not_mem {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (X : Finset V) {v : V} (hv : v ∉ X) : 2 ≤ cut_layer_potential G X v := by unfold cut_layer_potential rw [if_neg hv] split_ifs <;> norm_numlemma cut_layer_potential_lipschitz_eq_two {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (X : Finset V) {v : V} (hv : v ∉ X) (h : ∃ w ∈ X, G.Adj v w) : cut_layer_potential G X v = 2 := by unfold cut_layer_potential rw [if_neg hv, if_pos h]lemma cut_layer_potential_lipschitz_eq_one {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (X : Finset V) {v : V} (hv : v ∈ X) (h : ∃ w ∈ (Xᶜ : Finset V), G.Adj v w) : cut_layer_potential G X v = 1 := by unfold cut_layer_potential rw [if_pos hv, if_pos h]lemma cut_layer_potential_lipschitz_adj {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (X : Finset V) {u v : V} (h : G.Adj u v) : cut_layer_potential G X u - cut_layer_potential G X v ≤ 1 := by by_cases hu : u ∈ X · by_cases hv : v ∈ X · have := cut_layer_potential_lipschitz_of_mem G X hu have := cut_layer_potential_lipschitz_nonneg G X v linarith · have hfv := cut_layer_potential_lipschitz_eq_two G X hv ⟨u, hu, h.symm⟩ have := cut_layer_potential_lipschitz_of_mem G X hu linarith · by_cases hv : v ∈ X · have hfu := cut_layer_potential_lipschitz_eq_two G X hu ⟨v, hv, h⟩ have hfv := cut_layer_potential_lipschitz_eq_one G X hv ⟨u, Finset.mem_compl.mpr hu, h.symm⟩ linarith · have := cut_layer_potential_lipschitz_le_three G X u have := cut_layer_potential_lipschitz_of_not_mem G X hv linarithlemma cut_layer_potential_lipschitz_walk {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (X : Finset V) {u v : V} (p : G.Walk u v) : cut_layer_potential G X u - cut_layer_potential G X v ≤ (p.length : ℝ) := by induction p with | nil => simp | cons h q ih => rw [SimpleGraph.Walk.length_cons] push_cast have h1 := cut_layer_potential_lipschitz_adj G X h linarith/-- The 4-layer potential for any cut is 1-Lipschitz on any connected graph. -/theorem cut_layer_potential_lipschitz {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) (X : Finset V) (a b : V) : cut_layer_potential G X a - cut_layer_potential G X b ≤ (G.dist a b : ℝ) := by obtain ⟨p, hp⟩ := hG.exists_walk_length_eq_dist a b have h := cut_layer_potential_lipschitz_walk G X p rw [hp] at h exact h