cograph_is_distance_hereditary
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.
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.
uses
SimpleGraph.Reachable.exists_path_of_dist,SimpleGraph.Reachable.of_dist_ne_zeroby_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)
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.
uses
SimpleGraph.Walk.length_append,SimpleGraph.Walk.take_length,SimpleGraph.Walk.drop_length,Nat.min_eq_lefthave 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
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.
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)⟩
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.
uses
Subtype.ext,SimpleGraph.induce_adj.mp,SimpleGraph.induce_adj.mprrintro ⟨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)
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.
uses
SimpleGraph.Walk.length_map,cograph_is_distance_hereditary_dist_le_two,cograph_is_distance_hereditary_induceintro 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) _ _
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.
uses
Subtype.extby_cases heq : (↑u : α) = ↑v · have hv : v = u := (Subtype.ext heq).symm simp [hv]
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.
uses
SimpleGraph.dist_eq_one_iff_adj.mpr,SimpleGraph.induce_adj.mprhave 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)]
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.
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.
- In Lean's SimpleGraph library, the distance between two vertices that are not reachable from each other is defined to be 0 by convention, which is why the distance bound F.dist u v ≤ 2 holds unconditionally.
- The finiteness assumption [Fintype α] in the theorem signature is unused in the proof.
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.
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