AFTD Auto-Formalizing Theoretical Domains

tree_is_distance_hereditary

theoremverifiedformalization

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.

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

    lines 4–7

      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 : α)
  2. 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.

    lines 8–13

    uses Subtype.ext

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

    lines 15–23

    uses SimpleGraph.Walk.support_map, List.mem_map

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

    line 24

    uses le_antisymm

      refine le_antisymm ?_ ?_
  5. 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).

    lines 26–33

    uses SimpleGraph.Walk.length_map, SimpleGraph.Walk.map_induce, SimpleGraph.dist_le

        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
  6. 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).

    lines 35–37

    uses SimpleGraph.dist_le, SimpleGraph.Walk.length_map

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

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

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