AFTD Auto-Formalizing Theoretical Domains

wiener_index_bot

theoremverified

The Wiener index of the empty graph on any finite vertex type is zero.

Statement

theorem wiener_index_bot {V : Type*} [Fintype V] :
    wiener_index (⊥ : SimpleGraph V) = 0
Source
folklore
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • wiener_indexThe Wiener index of a finite simple graph G is the sum of the shortest-path distances between all unordered pairs of vertices in G.

Read back from the Lean

For every finite type V, the Wiener index of the empty graph (the graph with no edges, ⊥ : SimpleGraph V) is equal to 0.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The Wiener index of a graph is defined as the sum of the graph distances over all unordered pairs of vertices. In the empty graph $\bot$, the distance between any two vertices is zero. Since every term in the sum is zero, the sum vanishes, so the Wiener index is zero.

  1. It suffices to show that each term in the sum defining the Wiener index of the empty graph is zero.

    Unfolding the definition of `wiener_index` expresses the Wiener index as the sum over all unordered pairs $e \in \operatorname{Sym}^2(V)$ of the distance between their vertices in $\bot$. By `Finset.sum_eq_zero`, a finite sum vanishes if every summand is zero. We then introduce an arbitrary unordered pair $e$.

    lines 4–6

    uses wiener_index, Finset.sum_eq_zero

      rw [wiener_index]
      apply Finset.sum_eq_zero
      intro e _
  2. For any pair of vertices, the distance in the empty graph is zero, so every summand vanishes.

    By the induction principle `Sym2.ind`, any unordered pair $e$ can be written as $s(u, v)$ for some vertices $u, v \in V$. The distance function lifted to $s(u, v)$ evaluates to the graph distance $\bot.\operatorname{dist}(u, v)$. By `SimpleGraph.dist_bot`, the distance between any two vertices in the empty graph is zero, so simplifying closes the goal.

    lines 7–8

    uses Sym2.ind, SimpleGraph.dist_bot

      induction e using Sym2.ind with
      | _ u v => simp [SimpleGraph.dist_bot]
wiener_index
the definition of the Wiener index of a graph as the sum of distances between all unordered pairs of vertices
Finset.sum_eq_zero
a finite sum is zero if every term in the sum is zero
Sym2.ind
every unordered pair in $\operatorname{Sym}^2(V)$ can be represented as an explicit pair of elements $s(u, v)$
SimpleGraph.dist_bot
the graph distance between any two vertices in the empty graph $\bot$ is zero

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 Wiener index of the empty graph (bot) is 0. -/theorem wiener_index_bot {V : Type*} [Fintype V] :    wiener_index (⊥ : SimpleGraph V) = 0 := by  rw [wiener_index]  apply Finset.sum_eq_zero  intro e _  induction e using Sym2.ind with  | _ u v => simp [SimpleGraph.dist_bot]
See it in the graphDiscuss this resultChallenge it