graph_idle_measure_sum_eq_one
μ_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
- graph_lly_curvature_of_twinsIf x and y are adjacent and have the same neighbours apart from each other, then κ_LLY(x, y) = (d_x + 1)/d_x.
- not_edge_connectivity_ge_half_scale_mul_min_degree_mul_lly_lower_boundThe inequality κ'(G) ≥ (d/2) δ(G) κ_LLY^(d)(G) asked in OP-164 fails for d = 4: take a 4-cycle 0–1–2–3–0 and a triangle 4–5–6 joined by…
- graph_lly_curvature_of_leafIf x is a leaf of a finite connected graph whose only neighbour is y, then κ_LLY(x, y) = 2/d_y.
- graph_ollivier_curvature_div_le_two_div_distIn a finite connected graph, for x ≠ y and α ∈ [0, 1), κ_α(x, y)/(1 − α) ≤ 2/d(x, y).
- graph_lly_curvature_le_of_lipschitz_cut_potentialKantorovich-duality bound on the Lin–Lu–Yau curvature at a pair: for x ≠ y and any 1-Lipschitz potential f with f(x) − f(y) = d(x,y),…
- five_vertex_min_degree_two_wasserstein_lt_oneEvery connected graph on 5 vertices with minimum degree at least 2 has, for each edge xy, some α ∈ (0, 1) with W(μ_x^α, μ_y^α) < 1.
- five_vertex_t_star_wasserstein_geFor the T-graph and α in [0,1], 4/3 − α/3 ≤ W(μ_0^α, μ_1^α), because f(v) = d(v,2) is 1-Lipschitz and Σ f μ_0^α − Σ f μ_1^α = (2α +…
- graph_ollivier_curvature_div_monotoneOnIn a finite connected graph, for x ≠ y, α ↦ κ_α(x, y)/(1 − α) is nondecreasing on (0, 1).
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$.
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$.
uses
Finset.add_sum_erase,Finset.mem_univ,if_trueunfold graph_idle_measure rw [← Finset.add_sum_erase _ _ (Finset.mem_univ x)] simp only [if_true]
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$.
uses
Finset.sum_congr,if_neg,Finset.ne_of_mem_erase,Finset.sum_filterhave : ∑ 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]
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.
uses
SimpleGraph.mem_neighborFinsethave 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
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.
uses
Finset.sum_const,SimpleGraph.card_neighborFinset_eq_degree,nsmul_eq_mulrw [hf, Finset.sum_const, SimpleGraph.card_neighborFinset_eq_degree, nsmul_eq_mul]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.
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
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.
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