distance_hereditary_subsingleton
Every graph on at most one vertex is distance-hereditary.
Statement
theorem distance_hereditary_subsingleton {α : Type*} [Subsingleton α] (G : SimpleGraph α) : is_distance_hereditary G
- Source
- folklore
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- is_distance_hereditaryA graph F is distance-hereditary if for every induced subgraph and any two vertices reachable within it, their distance in the induced…
Read back from the Lean
For any type α that is a subsingleton (having at most one element) and any simple graph G on α, G is distance-hereditary (is_distance_hereditary G).
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
A graph is distance-hereditary if distances between reachable vertices in any induced subgraph agree with their distances in the original graph. Since the vertex type has at most one element, any two vertices in an induced subgraph must be equal. Consequently, both distances are self-distances, which are each zero.
Let $s \\subseteq \\alpha$ and let $u, v \\in s$ be vertices reachable from each other in the induced subgraph $G[s]$; it suffices to show that $\\operatorname{dist}_{G[s]}(u, v) = \\operatorname{dist}_G(u, v)$
By definition, a graph is distance-hereditary if for every induced subgraph $G[s]$ and every pair of vertices $u, v \\in s$ connected in $G[s]$, the distance between them in $G[s]$ equals their distance in $G$. We introduce the subset $s$, the vertices $u, v$, and the reachability hypothesis.
intro s u v _$u = v$, so the goal reduces to showing $\\operatorname{dist}_{G[s]}(u, u) = \\operatorname{dist}_G(u, u)$
Because the underlying vertex type $\\alpha$ is a subsingleton (having at most one element), the subtype $s$ is also a subsingleton, so any two elements $u$ and $v$ are equal by `Subsingleton.elim`. Substituting $v$ with $u$ transforms the goal into an equality between the self-distances.
uses
Subsingleton.elimhave hu : u = v := Subsingleton.elim u v subst hu
Both distances are zero, completing the proof
In any simple graph, the distance from any vertex to itself is $0$ by `SimpleGraph.dist_self`. Rewriting both the induced subgraph distance $\\operatorname{dist}_{G[s]}(u, u)$ and the full graph distance $\\operatorname{dist}_G(u, u)$ yields $0 = 0$.
uses
SimpleGraph.dist_selfrw [SimpleGraph.dist_self, SimpleGraph.dist_self]
Subsingleton.elim- in any type with at most one element, any two terms are equal
SimpleGraph.dist_self- in any simple graph, the distance from a vertex to itself is 0
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.
/-- Any graph on at most one vertex is distance-hereditary. -/theorem distance_hereditary_subsingleton {α : Type*} [Subsingleton α] (G : SimpleGraph α) : is_distance_hereditary G := by intro s u v _ have hu : u = v := Subsingleton.elim u v subst hu rw [SimpleGraph.dist_self, SimpleGraph.dist_self]