AFTD Auto-Formalizing Theoretical Domains

distance_hereditary_subsingleton

theoremverified

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.

  1. 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.

    line 4

      intro s u v _
  2. $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.

    lines 5–6

    uses Subsingleton.elim

      have hu : u = v := Subsingleton.elim u v
      subst hu
  3. 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$.

    line 7

    uses SimpleGraph.dist_self

      rw [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

/-- 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]
See it in the graphDiscuss this resultChallenge it