wiener_index_bot
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.
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$.
uses
wiener_index,Finset.sum_eq_zerorw [wiener_index] apply Finset.sum_eq_zero intro e _
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.
uses
Sym2.ind,SimpleGraph.dist_botinduction 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
- In Mathlib, graph distance `SimpleGraph.dist` returns a natural number, defaulting to `0` when no path exists between two vertices. Thus in the empty graph, where there are no edges, all pairwise distances are formally zero rather than infinite or undefined.
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.
/-- 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]