AFTD Auto-Formalizing Theoretical Domains

graph_idle_measure_nonneg

theoremverified

μ_x^α is nonnegative for 0 ≤ α ≤ 1.

Statement

theorem graph_idle_measure_nonneg {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (α : ℝ) (hα0 : 0 ≤ α) (hα1 : α ≤ 1) (x v : V) :
    0 ≤ graph_idle_measure G α x v
Source
Helper for the refutation of OP-165 (arXiv:2610.10559, after Theorem 1.4).
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 9

The proof, explained

The proof unfolds the definition of graph_idle_measure and splits into the three cases of its piecewise definition: when v = x, when v is a neighbor of x, and when v is neither equal nor adjacent to x. In each case, nonnegativity holds directly from the assumptions on α (0 ≤ α ≤ 1), the nonnegativity of graph degrees, and reflexivity of ≤.

  1. It suffices to verify nonnegativity across the three piecewise cases defining graph_idle_measure.

    Unfolding the definition of graph_idle_measure expands the term into nested conditionals: if v = x then α, else if G.Adj x v then (1 - α) / degree(x), else 0. The split_ifs tactic splits the proof into these three branches: v = x, v ≠ x with x adjacent to v, and v ≠ x with x not adjacent to v.

    lines 4–5

      unfold graph_idle_measure
      split_ifs
  2. When v = x, the measure is α, which is nonnegative.

    This follows directly from the theorem's hypothesis hα0, which states 0 ≤ α.

    line 6

      · exact hα0
  3. When v ≠ x and x is adjacent to v, the measure is (1 - α) / degree(x), which is nonnegative.

    By div_nonneg, a quotient is nonnegative whenever both the numerator and the denominator are nonnegative. The numerator 1 - α is nonnegative by linear arithmetic from the assumption α ≤ 1 (hα1), and the denominator degree(x) is nonnegative because graph degrees are natural numbers (Nat.cast_nonneg).

    line 7

    uses div_nonneg, Nat.cast_nonneg

      · exact div_nonneg (by linarith) (Nat.cast_nonneg _)
  4. When v ≠ x and x is not adjacent to v, the measure is 0, which is nonnegative.

    The remaining branch evaluates to 0, and 0 ≤ 0 holds reflexively by le_rfl.

    line 8

    uses le_rfl

      · exact le_rfl
div_nonneg
If a and b are nonnegative, their quotient a / b is nonnegative.
Nat.cast_nonneg
The coercion of any natural number into an ordered ring or semiring is nonnegative.
le_rfl
Less-than-or-equal is reflexive: a ≤ a for every a.

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_nonneg {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (α : ℝ) (hα0 : 0 ≤ α) (hα1 : α ≤ 1) (x v : V) :    0 ≤ graph_idle_measure G α x v := by  unfold graph_idle_measure  split_ifs  · exact hα0  · exact div_nonneg (by linarith) (Nat.cast_nonneg _)  · exact le_rfl
See it in the graphDiscuss this resultChallenge it