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
- cograph_is_distance_hereditaryEvery finite cograph is distance-hereditary.
- distance_hereditary_subsingletonEvery graph on at most one vertex is distance-hereditary.
- tree_is_distance_hereditaryEvery tree is distance-hereditary.
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