cut_layer_potential_diff_eq_three
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$.
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`.
uses
if_neg,if_possimp only [cut_layer_potential] have hxnot : x ∉ X := by simpa using hx rw [if_neg hxnot, if_pos hy]
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)$.
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
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$.
uses
if_negrw [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
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.
/-- 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