AFTD Auto-Formalizing Theoretical Domains

graph_idle_measure_sum_eq_one

theoremverified

μ_x^α is a probability measure (total mass 1) when x has a neighbour.

Statement

theorem graph_idle_measure_sum_eq_one {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (α : ℝ) (x : V) (hx : 0 < G.degree x) :
    ∑ v, graph_idle_measure G α x v = 1
Source
Sanity check of the definitions of arXiv:2610.10559 (Edge-Connectivity versus Lin--Lu--Yau Curvature), Sec. 2.2.
Verified
10 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • graph_idle_measureThe lazy random-walk measure μ_x^α at x with idleness α: mass α at x, (1 − α)/d_x at each neighbour of x, 0 elsewhere.
Used by 8

The proof, explained

We evaluate the sum of the transition probabilities $\mu_x^\alpha(v)$ over all vertices $v$ by splitting the sum into the vertex $x$ itself and all other vertices $v \neq x$. The self-transition term yields $\alpha$, while for $v \neq x$ the summand simplifies to $(1 - \alpha)/\deg(x)$ if $v$ is adjacent to $x$ and $0$ otherwise. Since a simple graph has no self-loops, the vertices in $V \setminus \{x\}$ adjacent to $x$ are precisely the neighbors of $x$. Summing the constant $(1 - \alpha)/\deg(x)$ over these $\deg(x)$ neighbors contributes $1 - \alpha$, which adds with $\alpha$ to give a total measure of $1$.

  1. The total sum decomposes into $\alpha$ plus the sum of the measure over all vertices $v \neq x$.

    Unfolding the definition of graph_idle_measure, the sum over all vertices in $V$ is split using Finset.add_sum_erase and Finset.mem_univ into the single term at $v = x$ and the sum over the remaining vertices in $V \setminus \{x\}$. At $v = x$, the condition $x = x$ is trivially true, so if_true simplifies that term to $\alpha$.

    lines 4–6

    uses Finset.add_sum_erase, Finset.mem_univ, if_true

      unfold graph_idle_measure
      rw [← Finset.add_sum_erase _ _ (Finset.mem_univ x)]
      simp only [if_true]
  2. The sum over $v \neq x$ reduces to summing $(1 - \alpha) / \deg(x)$ over the vertices in $V \setminus \{x\}$ that are adjacent to $x$.

    For each vertex $v \in V \setminus \{x\}$, the condition $v = x$ is false by Finset.ne_of_mem_erase, so if_neg drops the outer conditional, leaving only the neighbor check. Finset.sum_congr justifies replacing the summand with this simplified form over $V \setminus \{x\}$. Then Finset.sum_filter converts this conditional sum into a sum of the constant $(1 - \alpha) / \deg(x)$ over the filtered set of vertices adjacent to $x$.

    lines 7–11

    uses Finset.sum_congr, if_neg, Finset.ne_of_mem_erase, Finset.sum_filter

      have : ∑ v ∈ Finset.univ.erase x, (if v = x then α else if G.Adj x v then (1 - α) / (G.degree x : ℝ) else 0)
          = ∑ v ∈ Finset.univ.erase x, (if G.Adj x v then (1 - α) / (G.degree x : ℝ) else 0) := by
        refine Finset.sum_congr rfl fun v hv => ?_
        rw [if_neg (Finset.ne_of_mem_erase hv)]
      rw [this, ← Finset.sum_filter]
  3. The set of vertices in $V \setminus \{x\}$ adjacent to $x$ is equal to the neighbor finset of $x$.

    By set extensionality, a vertex belongs to the filtered set if and only if it is in $V \setminus \{x\}$ and adjacent to $x$. Adjacency is equivalent to membership in the neighbor finset by SimpleGraph.mem_neighborFinset. Furthermore, because simple graphs contain no self-loops, adjacency implies $v \neq x$, so the condition $v \in V \setminus \{x\}$ holds automatically.

    lines 12–14

    uses SimpleGraph.mem_neighborFinset

      have hf : (Finset.univ.erase x).filter (G.Adj x) = G.neighborFinset x := by
        ext v; simp [SimpleGraph.mem_neighborFinset]
        intro h; exact (G.ne_of_adj h).symm
  4. The sum of the constant over the neighbor set evaluates to $\deg(x) \cdot \frac{1 - \alpha}{\deg(x)}$.

    Rewriting the summation index to the neighbor finset, Finset.sum_const evaluates the constant sum as the size of the neighbor set times $(1 - \alpha) / \deg(x)$. By SimpleGraph.card_neighborFinset_eq_degree, this cardinality is $\deg(x)$, and nsmul_eq_mul converts natural scalar multiplication to multiplication in the real numbers.

    line 15

    uses Finset.sum_const, SimpleGraph.card_neighborFinset_eq_degree, nsmul_eq_mul

      rw [hf, Finset.sum_const, SimpleGraph.card_neighborFinset_eq_degree, nsmul_eq_mul]
  5. The total sum evaluates to $1$.

    Since the degree of $x$ is assumed strictly positive ($0 < \deg(x)$), its cast to $\mathbb{R}$ is non-zero. The field_simp tactic cancels the factor of $\deg(x)$ in the numerator and denominator, reducing the goal to $\alpha + (1 - \alpha) = 1$, which ring verifies.

    lines 16–18

      have : (G.degree x : ℝ) ≠ 0 := by exact_mod_cast hx.ne'
      field_simp
      ring
Finset.add_sum_erase
For an element $a$ in a finite set $s$, summing $f$ over $s$ equals $f(a)$ plus the sum of $f$ over $s \setminus \{a\}$.
Finset.mem_univ
Every element of a finite type belongs to its universal finset.
if_true
An if-then-else expression whose condition is True evaluates to the first branch.
Finset.sum_congr
Two sums over finite sets are equal if the index sets are equal and the summands agree at every element.
if_neg
An if-then-else expression whose condition is False evaluates to the second branch.
Finset.ne_of_mem_erase
An element belonging to $s \setminus \{a\}$ is not equal to $a$.
Finset.sum_filter
Summing a function over the elements of $s$ satisfying predicate $p$ equals summing an if-then-else expression over all of $s$.
SimpleGraph.mem_neighborFinset
A vertex $w$ belongs to the neighbor finset of $v$ if and only if $v$ and $w$ are adjacent in $G$.
Finset.sum_const
Summing a constant value over a finite set equals the cardinality of the set multiplied by that constant.
SimpleGraph.card_neighborFinset_eq_degree
The cardinality of the neighbor finset of a vertex $v$ equals the degree of $v$.
nsmul_eq_mul
Scalar multiplication of a ring element by a natural number $n$ equals standard multiplication by $n$ coerced into the ring.

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

theorem graph_idle_measure_sum_eq_one {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (α : ℝ) (x : V) (hx : 0 < G.degree x) :    ∑ v, graph_idle_measure G α x v = 1 := by  unfold graph_idle_measure  rw [← Finset.add_sum_erase _ _ (Finset.mem_univ x)]  simp only [if_true]  have : ∑ v ∈ Finset.univ.erase x, (if v = x then α else if G.Adj x v then (1 - α) / (G.degree x : ℝ) else 0)      = ∑ v ∈ Finset.univ.erase x, (if G.Adj x v then (1 - α) / (G.degree x : ℝ) else 0) := by    refine Finset.sum_congr rfl fun v hv => ?_    rw [if_neg (Finset.ne_of_mem_erase hv)]  rw [this, ← Finset.sum_filter]  have hf : (Finset.univ.erase x).filter (G.Adj x) = G.neighborFinset x := by    ext v; simp [SimpleGraph.mem_neighborFinset]    intro h; exact (G.ne_of_adj h).symm  rw [hf, Finset.sum_const, SimpleGraph.card_neighborFinset_eq_degree, nsmul_eq_mul]  have : (G.degree x : ℝ) ≠ 0 := by exact_mod_cast hx.ne'  field_simp  ring
See it in the graphDiscuss this resultChallenge it