AFTD Auto-Formalizing Theoretical Domains

cut_layer_potential_diff_eq_three

theoremverified

For any vertex x ∈ Xᶜ with no neighbours in X and y ∈ X with no neighbours in Xᶜ, cut_layer_potential G X x - cut_layer_potential G X y = 3.

Statement

theorem cut_layer_potential_diff_eq_three
    {V : Type} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj]
    (X : Finset V) (x y : V)
    (hx : x ∈ (Xᶜ : Finset V)) (hx_no : ∀ u ∈ X, ¬ G.Adj x u)
    (hy : y ∈ X) (hy_no : ∀ w ∈ (Xᶜ : Finset V), ¬ G.Adj y w) :
    cut_layer_potential G X x - cut_layer_potential G X y = 3
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 proof evaluates the 4-layer potential `cut_layer_potential G X` directly at both vertices by expanding its definition and resolving the conditional branches. Because $x \in X^c$ and has no neighbours in $X$, its potential evaluates to 3. Symmetrically, because $y \in X$ and has no neighbours in $X^c$, its potential evaluates to 0. The claim then reduces to the simple arithmetic difference $3 - 0 = 3$.

  1. Unfolding the cut layer potential reduces the difference to evaluating whether $x$ and $y$ have neighbours across the cut.

    Unfolding `cut_layer_potential` expands each term into a nested conditional: the outer condition checks membership in $X$, and the inner condition checks whether the vertex has an adjacent neighbour across the cut. From the hypothesis $x \in X^c$, we obtain $x \notin X$, so the outer conditional for $x$ selects the false branch via `if_neg`. Since $y \in X$, the outer conditional for $y$ selects the true branch via `if_pos`.

    lines 9–11

    uses if_neg, if_pos

      simp only [cut_layer_potential]
      have hxnot : x ∉ X := by simpa using hx
      rw [if_neg hxnot, if_pos hy]
  2. Neither $x$ has a neighbour in $X$ nor $y$ has a neighbour in $X^c$, rephrased as negated existential statements.

    The universal hypothesis `hx_no` states that every vertex in $X$ is non-adjacent to $x$; introducing an assumed witness $u \in X$ adjacent to $x$ yields an immediate contradiction, proving $\neg \exists u \in X, G.\mathrm{Adj}(x, u)$. Symmetrically, `hy_no` implies $\neg \exists w \in X^c, G.\mathrm{Adj}(y, w)$.

    lines 12–15

      have hx_no' : ¬ ∃ u ∈ X, G.Adj x u := by
        rintro ⟨u, hu, hadj⟩; exact hx_no u hu hadj
      have hy_no' : ¬ ∃ w ∈ (Xᶜ : Finset V), G.Adj y w := by
        rintro ⟨w, hw, hadj⟩; exact hy_no w hw hadj
  3. The potential at $x$ is 3, the potential at $y$ is 0, and their difference is 3.

    Rewriting with the negated existential hypotheses using `if_neg` selects the alternate branches of the remaining conditionals, evaluating the potential at $x$ to 3 and at $y$ to 0. Elementary arithmetic closes the resulting goal $3 - 0 = 3$.

    lines 16–17

    uses if_neg

      rw [if_neg hx_no', if_neg hy_no']
      norm_num
if_neg
A conditional expression `if c then t else e` evaluates to `e` when `c` is false.
if_pos
A conditional expression `if c then t else e` evaluates to `t` when `c` is true.

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

/-- The 4-layer potential evaluates to 3 on any interior vertex of Xᶜ and 0 on any interior vertex of X, giving difference 3. -/theorem cut_layer_potential_diff_eq_three    {V : Type} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj]    (X : Finset V) (x y : V)    (hx : x ∈ (Xᶜ : Finset V)) (hx_no : ∀ u ∈ X, ¬ G.Adj x u)    (hy : y ∈ X) (hy_no : ∀ w ∈ (Xᶜ : Finset V), ¬ G.Adj y w) :    cut_layer_potential G X x - cut_layer_potential G X y = 3 := by  simp only [cut_layer_potential]  have hxnot : x ∉ X := by simpa using hx  rw [if_neg hxnot, if_pos hy]  have hx_no' : ¬ ∃ u ∈ X, G.Adj x u := by    rintro ⟨u, hu, hadj⟩; exact hx_no u hu hadj  have hy_no' : ¬ ∃ w ∈ (Xᶜ : Finset V), G.Adj y w := by    rintro ⟨w, hw, hadj⟩; exact hy_no w hw hadj  rw [if_neg hx_no', if_neg hy_no']  norm_num
See it in the graphDiscuss this resultChallenge it