tree_is_distance_hereditary
Every tree is distance-hereditary.
Statement
theorem tree_is_distance_hereditary {α : Type*} (T : SimpleGraph α) (hT : T.IsTree) : is_distance_hereditary T
- Formalizes
- Howarka 1977
- 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 α and any simple graph T on α, if T is a tree (T.IsTree), then T is distance-hereditary (is_distance_hereditary T).
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
To show that a tree T is distance-hereditary, let s be any subset of vertices and let u, v ∈ s be reachable in the induced subgraph T[s]. A shortest walk p in T[s] between u and v is a path, and its image under the inclusion into T remains a simple path between u and v. Since simple paths in a tree are unique, this image must coincide with the unique shortest path q between u and v in T, which implies that every vertex of q lies in s. Consequently, q can be pulled back to a walk in T[s], showing that the distance in T[s] is at most the distance in T; the reverse inequality follows because p embeds as a walk in T.
Let s be a vertex subset and u, v ∈ s be vertices reachable in the induced subgraph T[s]; choose shortest paths p in T[s] and q in T between u and v.
Unfolding the definition of a distance-hereditary graph, we fix a subset s and vertices u, v ∈ s reachable in the induced subgraph T[s]. By huv.exists_path_of_dist, there is a path p in T[s] between u and v whose length equals the induced graph distance dist_{T[s]}(u, v). Since T is a tree, it is connected, so there is also a path q in T between u and v of length dist_T(u, v).
intro s u v huv -- A shortest walk `p` inside the induced subgraph, and the unique `T`-path `q` between `u` and `v`. obtain ⟨p, hppath, hplen⟩ := huv.exists_path_of_dist obtain ⟨q, hqpath, hqlen⟩ := hT.connected.exists_path_of_dist (u : α) (v : α)
The path p, pushed forward into T along the inclusion, is equal to q.
The canonical embedding of T[s] into T is injective because two subtype elements with the same underlying value are equal (Subtype.ext). An injective graph homomorphism sends paths to paths, so the image of p in T is a simple path from u to v. In a tree, the simple path between any two vertices is unique, so this pushed-forward path must be identical to q.
uses
Subtype.exthave hinj : Function.Injective (⇑(SimpleGraph.Embedding.induce s : T.induce s ↪g T)) := fun a b h => Subtype.ext h have hpT : (p.map (SimpleGraph.Embedding.induce s).toHom).IsPath := hppath.map hinj -- Uniqueness of paths in a tree: the image of `p` in `T` is already the `T`-path from `u` to `v`. have hEq : p.map (SimpleGraph.Embedding.induce s).toHom = q := (hT.existsUnique_path (u : α) (v : α)).unique hpT hqpath
Every vertex visited by q belongs to s.
Because q equals the image of p under the subtype inclusion, the vertex support of q is the image of the support of p under that inclusion (SimpleGraph.Walk.support_map). By List.mem_map, any vertex x on q is the underlying vertex of some element y on p. Since y belongs to the subtype s, its underlying vertex x lies in s.
uses
SimpleGraph.Walk.support_map,List.mem_maphave hsupp : ∀ x ∈ q.support, x ∈ s := by intro x hx have h1 : q.support = p.support.map (fun y : s => (y : α)) := by rw [← hEq] exact SimpleGraph.Walk.support_map _ p rw [h1] at hx simp only [List.mem_map] at hx obtain ⟨y, hy, rfl⟩ := hx exact y.2
To prove dist_{T[s]}(u, v) = dist_T(u, v), it suffices to prove dist_{T[s]}(u, v) ≤ dist_T(u, v) and dist_T(u, v) ≤ dist_{T[s]}(u, v).
By the antisymmetry of the partial order on natural numbers (le_antisymm), an equality of distances follows from establishing both inequalities.
uses
le_antisymmrefine le_antisymm ?_ ?_dist_{T[s]}(u, v) ≤ dist_T(u, v).
Because all vertices of q lie in s, q can be lifted to a walk in the induced subgraph T[s] (q.induce s hsupp). Pushing this lifted walk back into T recovers q (SimpleGraph.Walk.map_induce) and preserves walk length (SimpleGraph.Walk.length_map), so the lifted walk has length equal to that of q. Since the distance in T[s] is bounded by the length of any walk in T[s] (SimpleGraph.dist_le), and the length of q is dist_T(u, v), we conclude dist_{T[s]}(u, v) ≤ dist_T(u, v).
uses
SimpleGraph.Walk.length_map,SimpleGraph.Walk.map_induce,SimpleGraph.dist_lehave hlen : (q.induce s hsupp).length = q.length := by rw [← SimpleGraph.Walk.length_map (SimpleGraph.Embedding.induce s).toHom (q.induce s hsupp), SimpleGraph.Walk.map_induce] rfl have h : (T.induce s).dist ⟨(u:α), hsupp _ q.start_mem_support⟩ ⟨(v:α), hsupp _ q.end_mem_support⟩ ≤ (q.induce s hsupp).length := SimpleGraph.dist_le _ rw [hlen, hqlen] at h exact h
dist_T(u, v) ≤ dist_{T[s]}(u, v).
The image of p in T is a walk from u to v, so the distance dist_T(u, v) is at most its length (SimpleGraph.dist_le). Since pushing forward a walk preserves its length (SimpleGraph.Walk.length_map), and p has length dist_{T[s]}(u, v), we obtain dist_T(u, v) ≤ dist_{T[s]}(u, v).
uses
SimpleGraph.dist_le,SimpleGraph.Walk.length_mapcalc T.dist (u : α) (v : α) ≤ (p.map (SimpleGraph.Embedding.induce s).toHom).length := SimpleGraph.dist_le _ _ = (T.induce s).dist u v := by rw [SimpleGraph.Walk.length_map, hplen]
Subtype.ext- Two elements of a subtype are equal if their underlying values in the ambient type are equal.
SimpleGraph.Walk.support_map- Under a graph homomorphism, the list of vertices (support) of the mapped walk is the image of the original walk's vertex list under the homomorphism.
List.mem_map- An element belongs to the image of a list under a function if and only if it is the image of some element in that list.
le_antisymm- In a partial order, if a ≤ b and b ≤ a, then a = b.
SimpleGraph.Walk.length_map- Mapping a walk under a graph homomorphism preserves its length.
SimpleGraph.Walk.map_induce- Lifting a walk whose vertices all lie in a set s to the induced subgraph on s and then mapping it back to the ambient graph recovers the original walk.
SimpleGraph.dist_le- The graph distance between two vertices is less than or equal to the length of any walk between them.
- In Lean, the induced subgraph T.induce s has vertex type s (the subtype of vertices in s), requiring explicit conversions (such as SimpleGraph.Embedding.induce s and subtype membership proofs) between walks and vertices in the induced subgraph and those in T. On paper, these inclusions are treated implicitly.
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.
/-- Every tree is distance-hereditary. -/theorem tree_is_distance_hereditary {α : Type*} (T : SimpleGraph α) (hT : T.IsTree) : is_distance_hereditary T := by intro s u v huv -- A shortest walk `p` inside the induced subgraph, and the unique `T`-path `q` between `u` and `v`. obtain ⟨p, hppath, hplen⟩ := huv.exists_path_of_dist obtain ⟨q, hqpath, hqlen⟩ := hT.connected.exists_path_of_dist (u : α) (v : α) have hinj : Function.Injective (⇑(SimpleGraph.Embedding.induce s : T.induce s ↪g T)) := fun a b h => Subtype.ext h have hpT : (p.map (SimpleGraph.Embedding.induce s).toHom).IsPath := hppath.map hinj -- Uniqueness of paths in a tree: the image of `p` in `T` is already the `T`-path from `u` to `v`. have hEq : p.map (SimpleGraph.Embedding.induce s).toHom = q := (hT.existsUnique_path (u : α) (v : α)).unique hpT hqpath -- Hence every vertex of `q` lies in `s`. have hsupp : ∀ x ∈ q.support, x ∈ s := by intro x hx have h1 : q.support = p.support.map (fun y : s => (y : α)) := by rw [← hEq] exact SimpleGraph.Walk.support_map _ p rw [h1] at hx simp only [List.mem_map] at hx obtain ⟨y, hy, rfl⟩ := hx exact y.2 refine le_antisymm ?_ ?_ · -- `q` can be pushed into the induced subgraph, giving a walk there of length `T.dist u v`. have hlen : (q.induce s hsupp).length = q.length := by rw [← SimpleGraph.Walk.length_map (SimpleGraph.Embedding.induce s).toHom (q.induce s hsupp), SimpleGraph.Walk.map_induce] rfl have h : (T.induce s).dist ⟨(u:α), hsupp _ q.start_mem_support⟩ ⟨(v:α), hsupp _ q.end_mem_support⟩ ≤ (q.induce s hsupp).length := SimpleGraph.dist_le _ rw [hlen, hqlen] at h exact h · -- Conversely, `p` is a walk of `T`, so it bounds `T.dist u v`. calc T.dist (u : α) (v : α) ≤ (p.map (SimpleGraph.Embedding.induce s).toHom).length := SimpleGraph.dist_le _ _ = (T.induce s).dist u v := by rw [SimpleGraph.Walk.length_map, hplen]