AFTD Auto-Formalizing Theoretical Domains

five_vertex_min_degree_two_wasserstein_lt_one

theoremverified

Every connected graph on 5 vertices with minimum degree at least 2 has, for each edge xy, some α ∈ (0, 1) with W(μ_x^α, μ_y^α) < 1.

Statement

theorem five_vertex_min_degree_two_wasserstein_lt_one {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (hcard : Fintype.card V = 5) (hG : G.Connected)
    (hδ : 2 ≤ G.minDegree) (x y : V) (hxy : G.Adj x y) :
    ∃ α : ℝ, 0 < α ∧ α < 1 ∧
      graph_wasserstein_dist G (graph_idle_measure G α x) (graph_idle_measure G α y) < 1
Source
step towards lly_positive_edge_connectivity_threshold_five
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8
Used by 2

The proof, explained

To show that every edge $xy$ admits some laziness parameter $\alpha \in (0,1)$ with $W(\mu_x^\alpha, \mu_y^\alpha) < 1$, the proof fixes $\alpha = 1/2$. On any 5-vertex graph with minimum degree at least 2, the diameter is at most 2, allowing the Wasserstein distance between probability measures on an edge to be bounded by $2 - 2S_0 - m_{xy}$, where $S_0$ is the shared probability mass and $m_{xy}$ is the unshared mass at the endpoints. A combinatorial bound specialized to 5-vertex graphs with $\delta \ge 2$ guarantees that $2S_0 + m_{xy} > 1$, which immediately implies $W(\mu_x^{1/2}, \mu_y^{1/2}) < 1$.

  1. It suffices to show that for the choice $\alpha = 1/2$, the Wasserstein distance between the lazy walk measures is strictly less than 1.

    The theorem asserts the existence of $\alpha \in (0, 1)$ such that $W(\mu_x^\alpha, \mu_y^\alpha) < 1$. The proof fixes $\alpha = 1/2$, checks $0 < 1/2$ and $1/2 < 1$ by numerical evaluation (`norm_num`), leaving the distance bound as the remaining goal.

    lines 7–9

      have _ := hG
      use 1 / 2
      refine ⟨by norm_num, by norm_num, ?_⟩
  2. The degrees of $x$ and $y$ are strictly positive.

    Because the minimum degree $\delta$ of $G$ is at least 2, and the degree of every vertex is at least the minimum degree (`G.minDegree_le_degree`), both $\deg(x)$ and $\deg(y)$ are at least 2, hence strictly positive by linear integer arithmetic (`omega`).

    lines 10–15

    uses G.minDegree_le_degree

      have hdeg_x : 0 < G.degree x := by
        have := G.minDegree_le_degree x
        omega
      have hdeg_y : 0 < G.degree y := by
        have := G.minDegree_le_degree y
        omega
  3. The lazy walk measures $\mu_x^{1/2}$ and $\mu_y^{1/2}$ are probability distributions on $V$.

    Since $0 \le 1/2 \le 1$, `graph_idle_measure_nonneg` ensures that both measures take non-negative values at every vertex. Since $\deg(x) > 0$ and $\deg(y) > 0$, `graph_idle_measure_sum_eq_one` shows that the probabilities of each measure sum to 1.

    lines 16–25

    uses graph_idle_measure_nonneg, graph_idle_measure_sum_eq_one

      have hμ_nonneg : ∀ a, 0 ≤ graph_idle_measure G (1 / 2) x a := by
        intro a
        exact graph_idle_measure_nonneg G (1 / 2) (by norm_num) (by norm_num) x a
      have hν_nonneg : ∀ b, 0 ≤ graph_idle_measure G (1 / 2) y b := by
        intro b
        exact graph_idle_measure_nonneg G (1 / 2) (by norm_num) (by norm_num) y b
      have hμ_sum : ∑ a, graph_idle_measure G (1 / 2) x a = 1 :=
        graph_idle_measure_sum_eq_one G (1 / 2) x hdeg_x
      have hν_sum : ∑ b, graph_idle_measure G (1 / 2) y b = 1 :=
        graph_idle_measure_sum_eq_one G (1 / 2) y hdeg_y
  4. The graph has diameter at most 2, so all pairwise distances are at most 2.

    By `five_vertex_min_degree_two_ediam_le_two`, any 5-vertex graph with minimum degree at least 2 has extended diameter at most 2. For any pair of vertices $a, b \in V$, the extended distance between them is bounded by the diameter (`SimpleGraph.edist_le_ediam`). Using `le_trans`, `ENat.toNat_le_of_le_natCast`, and `Nat.cast_le.mpr`, this converts to the real inequality $\operatorname{dist}(a, b) \le 2$.

    lines 26–31

    uses five_vertex_min_degree_two_ediam_le_two, SimpleGraph.edist_le_ediam, le_trans, ENat.toNat_le_of_le_natCast, Nat.cast_le.mpr

      have hediam : G.ediam ≤ 2 := five_vertex_min_degree_two_ediam_le_two G hcard hδ
      have hdist2 : ∀ a b : V, (G.dist a b : ℝ) ≤ 2 := by
        intro a b
        have hle : G.edist a b ≤ 2 := le_trans SimpleGraph.edist_le_ediam hediam
        have hnat : G.dist a b ≤ 2 := ENat.toNat_le_of_le_natCast hle
        exact Nat.cast_le.mpr hnat
  5. The distance between the adjacent vertices $x$ and $y$ is 1.

    Because $x$ and $y$ are adjacent, the graph distance $\operatorname{dist}(x, y)$ equals 1 by `G.dist_eq_one_iff_adj.mpr`.

    lines 32–34

    uses G.dist_eq_one_iff_adj.mpr

      have hxy_dist : (G.dist x y : ℝ) = 1 := by
        rw [G.dist_eq_one_iff_adj.mpr hxy]
        norm_num
  6. The Wasserstein distance satisfies $W(\mu_x^{1/2}, \mu_y^{1/2}) \le 2 - 2S_0 - m_{xy}$.

    Applying `wasserstein_dist_le_of_diameter_two` using the verified probability measure properties and the diameter-2 bound yields the coupling upper bound $W(\mu_x^{1/2}, \mu_y^{1/2}) \le 2 - 2S_0 - m_{xy}$, where $S_0$ is the total overlapping mass $\sum_v \min(\mu_x^{1/2}(v), \mu_y^{1/2}(v))$ and $m_{xy} = \min(\mu_1(x), \nu_1(y))$ is the unshared mass at the edge endpoints.

    lines 35–37

    uses wasserstein_dist_le_of_diameter_two

      have h_bound := wasserstein_dist_le_of_diameter_two G hdist2
        (graph_idle_measure G (1 / 2) x) (graph_idle_measure G (1 / 2) y)
        hμ_nonneg hν_nonneg hμ_sum hν_sum x y hxy_dist
  7. The Wasserstein distance $W(\mu_x^{1/2}, \mu_y^{1/2})$ is strictly less than 1.

    The combinatorial lemma `five_vertex_min_degree_two_idle_coupling_bound` establishes that $1 < 2S_0 + m_{xy}$. Linear arithmetic (`linarith`) combines this with the coupling upper bound $W(\mu_x^{1/2}, \mu_y^{1/2}) \le 2 - (2S_0 + m_{xy})$ to conclude $W(\mu_x^{1/2}, \mu_y^{1/2}) < 1$.

    lines 38–39

    uses five_vertex_min_degree_two_idle_coupling_bound

      have h_comb := five_vertex_min_degree_two_idle_coupling_bound G hcard hδ x y hxy
      linarith
G.minDegree_le_degree
In any graph, the degree of each vertex is bounded below by the minimum degree.
G.dist_eq_one_iff_adj.mpr
If two vertices in a simple graph are adjacent, the graph distance between them is 1.
SimpleGraph.edist_le_ediam
The extended distance between any pair of vertices is at most the extended diameter of the graph.
le_trans
The ordering relation $\le$ is transitive ($a \le b$ and $b \le c$ imply $a \le c$).
ENat.toNat_le_of_le_natCast
If an extended natural number $m \le n$ (with $n \in \mathbb{N}$), then $m$ converts to a natural number satisfying $m.\mathrm{toNat} \le n$.
Nat.cast_le.mpr
An inequality $m \le n$ between natural numbers implies the corresponding inequality $\uparrow m \le \uparrow n$ in the real numbers.
graph_idle_measure_nonneg
For any parameter $\alpha \in [0, 1]$, the lazy walk measure $\mu_x^\alpha$ takes non-negative values on all vertices.
graph_idle_measure_sum_eq_one
When a vertex $x$ has strictly positive degree, its lazy walk measure $\mu_x^\alpha$ sums to 1 over all vertices.
five_vertex_min_degree_two_ediam_le_two
Every simple graph on 5 vertices with minimum degree at least 2 has extended diameter at most 2.
wasserstein_dist_le_of_diameter_two
On a graph of diameter at most 2, the Wasserstein distance between probability measures $\mu$ and $\nu$ on an edge $xy$ is at most $2 - 2S_0 - m_{xy}$, where $S_0$ is the total overlapping mass and $m_{xy}$ is the minimum unshared mass at $x$ and $y$.
five_vertex_min_degree_two_idle_coupling_bound
In any 5-vertex graph with minimum degree at least 2, the idle measures with $\alpha = 1/2$ at adjacent vertices satisfy $2S_0 + m_{xy} > 1$.

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 geometric core of part (i): on 5 vertices with δ ≥ 2, every edge admits some α ∈ (0,1) where the two lazy measures are closer than 1 in W. Uses δ ≥ 2 = (n−1)/2 hence ediam ≤ 2, so all non-neighbour pairs are at distance exactly 2. -/theorem five_vertex_min_degree_two_wasserstein_lt_one {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (hcard : Fintype.card V = 5) (hG : G.Connected)    (hδ : 2 ≤ G.minDegree) (x y : V) (hxy : G.Adj x y) :    ∃ α : ℝ, 0 < α ∧ α < 1 ∧      graph_wasserstein_dist G (graph_idle_measure G α x) (graph_idle_measure G α y) < 1 := by  have _ := hG  use 1 / 2  refine ⟨by norm_num, by norm_num, ?_⟩  have hdeg_x : 0 < G.degree x := by    have := G.minDegree_le_degree x    omega  have hdeg_y : 0 < G.degree y := by    have := G.minDegree_le_degree y    omega  have hμ_nonneg : ∀ a, 0 ≤ graph_idle_measure G (1 / 2) x a := by    intro a    exact graph_idle_measure_nonneg G (1 / 2) (by norm_num) (by norm_num) x a  have hν_nonneg : ∀ b, 0 ≤ graph_idle_measure G (1 / 2) y b := by    intro b    exact graph_idle_measure_nonneg G (1 / 2) (by norm_num) (by norm_num) y b  have hμ_sum : ∑ a, graph_idle_measure G (1 / 2) x a = 1 :=    graph_idle_measure_sum_eq_one G (1 / 2) x hdeg_x  have hν_sum : ∑ b, graph_idle_measure G (1 / 2) y b = 1 :=    graph_idle_measure_sum_eq_one G (1 / 2) y hdeg_y  have hediam : G.ediam ≤ 2 := five_vertex_min_degree_two_ediam_le_two G hcard hδ  have hdist2 : ∀ a b : V, (G.dist a b : ℝ) ≤ 2 := by    intro a b    have hle : G.edist a b ≤ 2 := le_trans SimpleGraph.edist_le_ediam hediam    have hnat : G.dist a b ≤ 2 := ENat.toNat_le_of_le_natCast hle    exact Nat.cast_le.mpr hnat  have hxy_dist : (G.dist x y : ℝ) = 1 := by    rw [G.dist_eq_one_iff_adj.mpr hxy]    norm_num  have h_bound := wasserstein_dist_le_of_diameter_two G hdist2    (graph_idle_measure G (1 / 2) x) (graph_idle_measure G (1 / 2) y)    hμ_nonneg hν_nonneg hμ_sum hν_sum x y hxy_dist  have h_comb := five_vertex_min_degree_two_idle_coupling_bound G hcard hδ x y hxy  linarith
See it in the graphDiscuss this resultChallenge it