AFTD Auto-Formalizing Theoretical Domains

cograph_is_distance_hereditary

theoremverifiedformalization

Every finite cograph is distance-hereditary.

Statement

theorem cograph_is_distance_hereditary {α : Type*} [Fintype α] (F : SimpleGraph α)
    (hF : is_cograph F) : is_distance_hereditary F
Formalizes
arXiv:2610.13820, Fact 4.4
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • is_cographA graph F is a cograph if it does not contain an induced path on four vertices (P₄).
  • 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

Every finite cograph is distance-hereditary. That is, for every finite type α and every simple graph F on α, if F is a cograph (as defined by is_cograph), then F is distance-hereditary (as defined by is_distance_hereditary).

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

The proof shows that every cograph has diameter at most 2, because any shortest path of length 3 or more must be chordless (as chords would provide strictly shorter walks) and would therefore contain an induced path on four vertices (P₄), contradicting the definition of a cograph. Since induced subgraphs of cographs are also cographs, distances in both the ambient graph and any connected induced subgraph cannot exceed 2. Consequently, for any two vertices in an induced subgraph, their distances in both graphs must agree: they are 0 if the vertices are identical, 1 if they are adjacent, and 2 if they are distinct and non-adjacent.

  1. If the distance between u and v is greater than 2, there exists a chordless path p between them of length at least 3 with distinct vertices.

    Assuming for contradiction that F.dist u v > 2, the distance is non-zero, so u and v are reachable by SimpleGraph.Reachable.of_dist_ne_zero. Thus SimpleGraph.Reachable.exists_path_of_dist yields a path p from u to v of length equal to F.dist u v ≥ 3. Because p is a path, its vertex indexing is injective, so p.getVert i ≠ p.getVert j whenever i ≠ j.

    lines 3–12

    uses SimpleGraph.Reachable.exists_path_of_dist, SimpleGraph.Reachable.of_dist_ne_zero

      by_contra h
      have hne : F.dist u v ≠ 0 := by omega
      obtain ⟨p, hp, hlen⟩ := SimpleGraph.Reachable.exists_path_of_dist
        (SimpleGraph.Reachable.of_dist_ne_zero hne)
      have hlen3 : 3 ≤ p.length := by omega
      have hinj := hp.getVert_injOn
      have hdist : ∀ i j : ℕ, i ≤ p.length → j ≤ p.length → i ≠ j →
          p.getVert i ≠ p.getVert j := by
        intro i j hi hj hij heq
        exact hij (hinj hi hj heq)
  2. The path p has no chords between vertices at index distance at least 2.

    If there were an edge between p(i) and p(j) with i + 2 ≤ j, we could shortcut p by appending the prefix p[0..i], this chord edge, and the suffix p[j..length]. By SimpleGraph.Walk.length_append, SimpleGraph.Walk.take_length, SimpleGraph.Walk.drop_length, and Nat.min_eq_left, the length of this shortcut walk is i + 1 + (p.length - j) < p.length. But the graph distance is bounded above by any walk length, so F.dist u v ≤ length(shortcut) < p.length = F.dist u v, a contradiction.

    lines 13–23

    uses SimpleGraph.Walk.length_append, SimpleGraph.Walk.take_length, SimpleGraph.Walk.drop_length, Nat.min_eq_left

      have hchord : ∀ i j : ℕ, i + 2 ≤ j → j ≤ p.length → ¬ F.Adj (p.getVert i) (p.getVert j) := by
        intro i j hij hj hadj
        have hi : i ≤ p.length := by omega
        have hlen' : ((p.take i).append ((hadj.toWalk).append (p.drop j))).length
            = i + 1 + (p.length - j) := by
          simp [SimpleGraph.Walk.length_append, SimpleGraph.Walk.take_length,
            SimpleGraph.Walk.drop_length, Nat.min_eq_left hi]
          omega
        have hle := F.dist_le ((p.take i).append ((hadj.toWalk).append (p.drop j)))
        rw [hlen'] at hle
        omega
  3. Every cograph has diameter at most 2: for all vertices u and v, F.dist u v ≤ 2.

    The first four vertices p(0), p(1), p(2), p(3) of p are pairwise distinct and adjacent along the path (0~1, 1~2, 2~3). Because p has no chords, 0 is not adjacent to 2 or 3, and 1 is not adjacent to 3. These four vertices thus form an induced P₄, directly contradicting the hypothesis hF that F is a cograph.

    lines 24–34

      refine hF ⟨p.getVert 0, p.getVert 1, p.getVert 2, p.getVert 3,
        hdist 0 1 (by omega) (by omega) (by decide),
        hdist 0 2 (by omega) (by omega) (by decide),
        hdist 0 3 (by omega) (by omega) (by decide),
        hdist 1 2 (by omega) (by omega) (by decide),
        hdist 1 3 (by omega) (by omega) (by decide),
        hdist 2 3 (by omega) (by omega) (by decide),
        p.adj_getVert_succ (by omega), p.adj_getVert_succ (by omega),
        p.adj_getVert_succ (by omega),
        hchord 0 2 (by omega) (by omega), hchord 0 3 (by omega) (by omega),
        hchord 1 3 (by omega) (by omega)⟩
  4. Any induced subgraph of a cograph is also a cograph.

    Suppose an induced subgraph F[s] had an induced P₄ on vertices a, b, c, d ∈ s. By Subtype.ext, their underlying vertices in α are pairwise distinct. Adjacencies and non-adjacencies in F[s] match those in F via SimpleGraph.induce_adj.mp and SimpleGraph.induce_adj.mpr. Thus these four vertices would form an induced P₄ in F, contradicting that F is a cograph.

    lines 38–51

    uses Subtype.ext, SimpleGraph.induce_adj.mp, SimpleGraph.induce_adj.mpr

      rintro ⟨a, b, c, d, hab, hac, had, hbc, hbd, hcd, eab, ebc, ecd, nac, nad, nbd⟩
      refine hF ⟨a, b, c, d, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩
      · exact fun h => hab (Subtype.ext h)
      · exact fun h => hac (Subtype.ext h)
      · exact fun h => had (Subtype.ext h)
      · exact fun h => hbc (Subtype.ext h)
      · exact fun h => hbd (Subtype.ext h)
      · exact fun h => hcd (Subtype.ext h)
      · exact SimpleGraph.induce_adj.mp eab
      · exact SimpleGraph.induce_adj.mp ebc
      · exact SimpleGraph.induce_adj.mp ecd
      · exact fun h => nac (SimpleGraph.induce_adj.mpr h)
      · exact fun h => nad (SimpleGraph.induce_adj.mpr h)
      · exact fun h => nbd (SimpleGraph.induce_adj.mpr h)
  5. The distance in F is bounded above by the distance in the induced subgraph F[s], and both distances are at most 2.

    Mapping a shortest walk in F[s] along the inclusion homomorphism φ gives a walk in F of the same length by SimpleGraph.Walk.length_map, showing F.dist u v ≤ F[s].dist u v. Moreover, by cograph_is_distance_hereditary_dist_le_two, the distance in F is at most 2, and since F[s] is also a cograph by cograph_is_distance_hereditary_induce, the distance in F[s] is also at most 2.

    lines 56–68

    uses SimpleGraph.Walk.length_map, cograph_is_distance_hereditary_dist_le_two, cograph_is_distance_hereditary_induce

      intro s u v hreach
      let φ : (SimpleGraph.induce s F) →g F :=
        { toFun := Subtype.val, map_rel' := fun {x y} h => SimpleGraph.induce_adj.mp h }
      have hreachF : F.Reachable (↑u) (↑v) := hreach.map φ
      have h1 : F.dist (↑u) (↑v) ≤ (SimpleGraph.induce s F).dist u v := by
        obtain ⟨p, hp⟩ := hreach.exists_walk_length_eq_dist
        have h := F.dist_le (p.map φ)
        rw [SimpleGraph.Walk.length_map, hp] at h
        exact h
      have h2 : F.dist (↑u) (↑v) ≤ 2 := cograph_is_distance_hereditary_dist_le_two F hF _ _
      have h3 : (SimpleGraph.induce s F).dist u v ≤ 2 :=
        cograph_is_distance_hereditary_dist_le_two (SimpleGraph.induce s F)
          (cograph_is_distance_hereditary_induce F s hF) _ _
  6. If u = v, the distances in F[s] and F coincide.

    If the underlying vertices in α are equal, Subtype.ext shows that u = v in the induced subgraph, so both distances are 0.

    lines 69–71

    uses Subtype.ext

      by_cases heq : (↑u : α) = ↑v
      · have hv : v = u := (Subtype.ext heq).symm
        simp [hv]
  7. If u ≠ v and u, v are adjacent, the distances in F[s] and F coincide.

    Assuming u ≠ v, if u and v are adjacent in F, they are adjacent in F[s] by SimpleGraph.induce_adj.mpr. By SimpleGraph.dist_eq_one_iff_adj.mpr, both distances are equal to 1.

    lines 72–75

    uses SimpleGraph.dist_eq_one_iff_adj.mpr, SimpleGraph.induce_adj.mpr

      have huv : u ≠ v := fun h => heq (by rw [h])
      by_cases hadj : F.Adj (↑u) (↑v)
      · rw [SimpleGraph.dist_eq_one_iff_adj.mpr hadj,
          SimpleGraph.dist_eq_one_iff_adj.mpr (SimpleGraph.induce_adj.mpr hadj)]
  8. If u and v are distinct and non-adjacent, both distances equal 2, completing the proof.

    Because u ≠ v and they are reachable, both distances are strictly positive. Because they are not adjacent, SimpleGraph.dist_eq_one_iff_adj.mp and SimpleGraph.induce_adj.mp imply neither distance can be 1. Since both distances are natural numbers bounded above by 2, positive, and distinct from 1, both must equal 2, which omega verifies.

    lines 76–82

    uses SimpleGraph.dist_eq_one_iff_adj.mp, SimpleGraph.induce_adj.mp

      · have hpos1 : 0 < F.dist (↑u) (↑v) := hreachF.pos_dist_of_ne heq
        have hne1 : F.dist (↑u) (↑v) ≠ 1 := fun h =>
          hadj (SimpleGraph.dist_eq_one_iff_adj.mp h)
        have hpos2 : 0 < (SimpleGraph.induce s F).dist u v := hreach.pos_dist_of_ne huv
        have hne2 : (SimpleGraph.induce s F).dist u v ≠ 1 := fun h =>
          (fun hh => hadj (SimpleGraph.induce_adj.mp hh)) (SimpleGraph.dist_eq_one_iff_adj.mp h)
        omega
SimpleGraph.Reachable.exists_path_of_dist
Between any two reachable vertices in a graph, there exists a path (a walk with no repeated vertices) whose length equals the graph distance between them.
SimpleGraph.Reachable.of_dist_ne_zero
If the graph distance between two vertices is non-zero, then they are reachable from one another.
SimpleGraph.Walk.length_append
The length of the concatenation of two walks is the sum of their lengths.
SimpleGraph.Walk.take_length
The length of the prefix of a walk obtained by taking its first n edges is min(n, p.length).
SimpleGraph.Walk.drop_length
The length of the suffix of a walk obtained by dropping its first n edges is p.length - n.
Nat.min_eq_left
If a ≤ b, then min(a, b) = a.
Subtype.ext
Two elements of a subtype are equal if and only if their underlying values are equal.
SimpleGraph.induce_adj.mp
If two vertices in an induced subgraph are adjacent, their underlying vertices are adjacent in the ambient graph.
SimpleGraph.induce_adj.mpr
If two vertices of an induced subgraph are adjacent in the ambient graph, they are adjacent in the induced subgraph.
SimpleGraph.Walk.length_map
Mapping a walk along a graph homomorphism preserves its length.
cograph_is_distance_hereditary_dist_le_two
In any cograph, the graph distance between any two vertices is at most 2.
cograph_is_distance_hereditary_induce
Every induced subgraph of a cograph is also a cograph.
SimpleGraph.dist_eq_one_iff_adj.mpr
If two vertices in a graph are adjacent, the distance between them is 1.
SimpleGraph.dist_eq_one_iff_adj.mp
If the distance between two vertices in a graph is 1, then they are adjacent.

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

private lemma cograph_is_distance_hereditary_dist_le_two {α : Type*} (F : SimpleGraph α)    (hF : is_cograph F) (u v : α) : F.dist u v ≤ 2 := by  by_contra h  have hne : F.dist u v ≠ 0 := by omega  obtain ⟨p, hp, hlen⟩ := SimpleGraph.Reachable.exists_path_of_dist    (SimpleGraph.Reachable.of_dist_ne_zero hne)  have hlen3 : 3 ≤ p.length := by omega  have hinj := hp.getVert_injOn  have hdist : ∀ i j : ℕ, i ≤ p.length → j ≤ p.length → i ≠ j →      p.getVert i ≠ p.getVert j := by    intro i j hi hj hij heq    exact hij (hinj hi hj heq)  have hchord : ∀ i j : ℕ, i + 2 ≤ j → j ≤ p.length → ¬ F.Adj (p.getVert i) (p.getVert j) := by    intro i j hij hj hadj    have hi : i ≤ p.length := by omega    have hlen' : ((p.take i).append ((hadj.toWalk).append (p.drop j))).length        = i + 1 + (p.length - j) := by      simp [SimpleGraph.Walk.length_append, SimpleGraph.Walk.take_length,        SimpleGraph.Walk.drop_length, Nat.min_eq_left hi]      omega    have hle := F.dist_le ((p.take i).append ((hadj.toWalk).append (p.drop j)))    rw [hlen'] at hle    omega  refine hF ⟨p.getVert 0, p.getVert 1, p.getVert 2, p.getVert 3,    hdist 0 1 (by omega) (by omega) (by decide),    hdist 0 2 (by omega) (by omega) (by decide),    hdist 0 3 (by omega) (by omega) (by decide),    hdist 1 2 (by omega) (by omega) (by decide),    hdist 1 3 (by omega) (by omega) (by decide),    hdist 2 3 (by omega) (by omega) (by decide),    p.adj_getVert_succ (by omega), p.adj_getVert_succ (by omega),    p.adj_getVert_succ (by omega),    hchord 0 2 (by omega) (by omega), hchord 0 3 (by omega) (by omega),    hchord 1 3 (by omega) (by omega)⟩private lemma cograph_is_distance_hereditary_induce {α : Type*} (F : SimpleGraph α) (s : Set α)    (hF : is_cograph F) : is_cograph (SimpleGraph.induce s F) := by  rintro ⟨a, b, c, d, hab, hac, had, hbc, hbd, hcd, eab, ebc, ecd, nac, nad, nbd⟩  refine hF ⟨a, b, c, d, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩  · exact fun h => hab (Subtype.ext h)  · exact fun h => hac (Subtype.ext h)  · exact fun h => had (Subtype.ext h)  · exact fun h => hbc (Subtype.ext h)  · exact fun h => hbd (Subtype.ext h)  · exact fun h => hcd (Subtype.ext h)  · exact SimpleGraph.induce_adj.mp eab  · exact SimpleGraph.induce_adj.mp ebc  · exact SimpleGraph.induce_adj.mp ecd  · exact fun h => nac (SimpleGraph.induce_adj.mpr h)  · exact fun h => nad (SimpleGraph.induce_adj.mpr h)  · exact fun h => nbd (SimpleGraph.induce_adj.mpr h)/-- Every finite cograph is distance-hereditary. -/theorem cograph_is_distance_hereditary {α : Type*} [Fintype α] (F : SimpleGraph α)    (hF : is_cograph F) : is_distance_hereditary F := by  intro s u v hreach  let φ : (SimpleGraph.induce s F) →g F :=    { toFun := Subtype.val, map_rel' := fun {x y} h => SimpleGraph.induce_adj.mp h }  have hreachF : F.Reachable (↑u) (↑v) := hreach.map φ  have h1 : F.dist (↑u) (↑v) ≤ (SimpleGraph.induce s F).dist u v := by    obtain ⟨p, hp⟩ := hreach.exists_walk_length_eq_dist    have h := F.dist_le (p.map φ)    rw [SimpleGraph.Walk.length_map, hp] at h    exact h  have h2 : F.dist (↑u) (↑v) ≤ 2 := cograph_is_distance_hereditary_dist_le_two F hF _ _  have h3 : (SimpleGraph.induce s F).dist u v ≤ 2 :=    cograph_is_distance_hereditary_dist_le_two (SimpleGraph.induce s F)      (cograph_is_distance_hereditary_induce F s hF) _ _  by_cases heq : (↑u : α) = ↑v  · have hv : v = u := (Subtype.ext heq).symm    simp [hv]  have huv : u ≠ v := fun h => heq (by rw [h])  by_cases hadj : F.Adj (↑u) (↑v)  · rw [SimpleGraph.dist_eq_one_iff_adj.mpr hadj,      SimpleGraph.dist_eq_one_iff_adj.mpr (SimpleGraph.induce_adj.mpr hadj)]  · have hpos1 : 0 < F.dist (↑u) (↑v) := hreachF.pos_dist_of_ne heq    have hne1 : F.dist (↑u) (↑v) ≠ 1 := fun h =>      hadj (SimpleGraph.dist_eq_one_iff_adj.mp h)    have hpos2 : 0 < (SimpleGraph.induce s F).dist u v := hreach.pos_dist_of_ne huv    have hne2 : (SimpleGraph.induce s F).dist u v ≠ 1 := fun h =>      (fun hh => hadj (SimpleGraph.induce_adj.mp hh)) (SimpleGraph.dist_eq_one_iff_adj.mp h)    omega
See it in the graphDiscuss this resultChallenge it