AFTD Auto-Formalizing Theoretical Domains

cut_layer_potential_lipschitz

theoremverified

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.

  1. 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.

    lines 4–5

      unfold cut_layer_potential
      split_ifs <;> norm_num
  2. 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.

    lines 10–11

      unfold cut_layer_potential
      split_ifs <;> norm_num
  3. 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.

    lines 16–18

    uses if_pos

      unfold cut_layer_potential
      rw [if_pos hv]
      split_ifs <;> norm_num
  4. 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.

    lines 23–25

    uses if_neg

      unfold cut_layer_potential
      rw [if_neg hv]
      split_ifs <;> norm_num
  5. 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.

    lines 31–32

    uses if_neg, if_pos

      unfold cut_layer_potential
      rw [if_neg hv, if_pos h]
  6. 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.

    lines 38–39

    uses if_pos

      unfold cut_layer_potential
      rw [if_pos hv, if_pos h]
  7. 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.

    lines 44–51

    uses cut_layer_potential_lipschitz_of_mem, cut_layer_potential_lipschitz_nonneg, cut_layer_potential_lipschitz_eq_two

      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
  8. 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.

    lines 52–58

    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
  9. 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.

    lines 63–69

    uses SimpleGraph.Walk.length_cons, cut_layer_potential_lipschitz_adj

      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
  10. 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.

    lines 77–80

    uses cut_layer_potential_lipschitz_walk

      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
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.

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

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
See it in the graphDiscuss this resultChallenge it