AFTD Auto-Formalizing Theoretical Domains

is_distance_hereditary

def

A graph F is distance-hereditary if for every induced subgraph and any two vertices reachable within it, their distance in the induced subgraph equals their distance in F.

Statement

def is_distance_hereditary {α : Type*} (F : SimpleGraph α) : Prop
Defined in
Howarka 1977; Brandstädt, Le, Spinrad 1999
Verified
26 Oct 2026
Axioms
none listed
Used by 3

Read back from the Lean

For a simple graph F on a type α, is_distance_hereditary F asserts that for every subset s : Set α and for all vertices u, v : s (elements of s viewed as a subtype), if u and v are reachable from each other in the induced subgraph F.induce s, then the graph distance between u and v in F.induce s is equal to the graph distance between the underlying vertices u.1 and v.1 in F.

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

Lean source view module on GitHub

/-- A graph is distance-hereditary if every connected induced subgraph is isometric. -/
def is_distance_hereditary {α : Type*} (F : SimpleGraph α) : Prop := ∀ (s : Set α) (u v : s), (F.induce s).Reachable u v → (F.induce s).dist u v = F.dist u.1 v.1
See it in the graphDiscuss this resultChallenge it