Prove2Me
Navigate
DiscoverFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Corollary 10.8 -- the resistance triangle inequality

Proved
MarkovMixing.resistance_triangle

by Shuze Chen · Aug 21, 2026 · Mathlib 0df444a (Lean v4.33.1)

markov-chainsmixing-timesprobability

Let ccc be a network on a finite vertex set: a symmetric nonnegative conductance function with total conductance c(x)=∑yc(x,y)>0c(x)=\sum_yc(x,y)>0c(x)=∑y​c(x,y)>0 at every vertex, whose associated walk P(x,y)=c(x,y)/c(x)P(x,y)=c(x,y)/c(x)P(x,y)=c(x,y)/c(x) is irreducible. For distinct vertices, the effective resistance R(a↔z)R(a\leftrightarrow z)R(a↔z) is defined through the voltage W(x)=Px{τa<τz}W(x)=\mathbb P_x\{\tau_a<\tau_z\}W(x)=Px​{τa​<τz​} and the current ∥I∥=∑yc(a,y)[W(a)−W(y)]\|I\|=\sum_yc(a,y)[W(a)-W(y)]∥I∥=∑y​c(a,y)[W(a)−W(y)] as R(a↔z)=∥I∥−1R(a\leftrightarrow z)=\|I\|^{-1}R(a↔z)=∥I∥−1.

The theorem (Corollary 10.8 of Levin–Peres–Wilmer) asserts that effective resistance satisfies the triangle inequality: for pairwise distinct vertices a,b,za,b,za,b,z,

R(a↔z)  ≤  R(a↔b)+R(b↔z).R(a\leftrightarrow z)\;\le\;R(a\leftrightarrow b)+R(b\leftrightarrow z).R(a↔z)≤R(a↔b)+R(b↔z).

Together with symmetry and positivity this makes RRR a genuine metric on the vertices of a connected network — the resistance metric. In the book it is a direct consequence of the commute time identity, which converts the claim into the sub-additivity of round-trip times through the intermediate vertex bbb.

Preamble
import Definitions.Def_mm_network
Formal statement
namespace MarkovMixing

/-- **Corollary 10.8** (LPW): effective resistance satisfies the triangle
inequality `R(a↔c) ≤ R(a↔b) + R(b↔c)`. -/
theorem resistance_triangle {V : Type*} [Fintype V] [DecidableEq V]
    (c : V → V → ℝ) (hc : IsConductance c)
    (hpos : ∀ x : V, 0 < vertexConductance c x)
    (hirr : Irreducible (networkWalk c)) (a b z : V)
    (hab : a ≠ b) (hbz : b ≠ z) (haz : a ≠ z) :
    effectiveResistance c a z ≤
      effectiveResistance c a b + effectiveResistance c b z := by
  sorry

end MarkovMixing
Source
D. A. Levin, Y. Peres, E. L. Wilmer, Markov Chains and Mixing Times, AMS 2009, https://documents.epfl.ch/groups/i/ip/ipg/www/2013-2014/Random_Walks/markovmixing.pdf, Section 10.3, Corollary 10.8, Eq. (10.10), p. 131

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paper
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me