AFTD Auto-Formalizing Theoretical Domains

exists_triangle_free_all_powers_well_covered_diam_eq_three

theoremverifiedoriginal

There exists a finite connected triangle-free simple graph G with at least two vertices whose diameter is exactly 3 and such that every positive integer power G^d (for d ≥ 1) is well-covered.

Statement

theorem exists_triangle_free_all_powers_well_covered_diam_eq_three :
    ∃ (V : Type) (_ : Fintype V) (G : SimpleGraph V),
      G.Connected ∧
      G.CliqueFree 3 ∧
      2 ≤ Fintype.card V ∧
      G.diam = 3 ∧
      (∀ d : ℕ, 1 ≤ d → simple_graph_is_well_covered (simple_graph_power G d))
Related work
arXiv:2610.09300, Example 3.8
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4

Read back from the Lean

There exist a finite type $V$ and a simple graph $G$ on $V$ such that: 1. $G$ is connected; 2. $G$ is clique-free of size 3 (i.e., triangle-free); 3. the number of vertices of $V$ is at least 2; 4. the diameter of $G$ is equal to 3; and 5. for every natural number $d \ge 1$, the $d$-th power of $G$ is well-covered.

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 theorem is witnessed by the 7-cycle graph C_7, which is a finite connected triangle-free simple graph with diameter 3. To prove that all positive powers C_7^d (for d ≥ 1) are well-covered, the proof applies a general reduction showing that for any connected graph of diameter at most 3, it suffices to check that the graph itself and its square are well-covered. Well-coveredness of C_7 and C_7^2 is established by using exhaustive decision procedures to show that every maximal independent set has cardinality 3 in C_7 and cardinality 2 in C_7^2.

  1. The relation defining the square graph of C_7 is symmetric and loopless, hence forms a valid simple graph on Fin 7.

    Symmetry holds because distinctness is symmetric, adjacency in C_7 is symmetric, and intersection of neighbor sets is commutative (via `Finset.inter_comm`). Looplessness holds because no vertex is distinct from itself.

    lines 3–9

    uses Finset.inter_comm

      symm := ⟨by
        intro u v h
        refine ⟨h.1.symm, ?_⟩
        rcases h.2 with h1 | h2
        · left; exact h1.symm
        · right; rw [Finset.inter_comm]; exact h2⟩
      loopless := ⟨by intro u h; exact h.1 rfl⟩
  2. Adjacency in the explicit square graph of C_7 is decidable.

    Adjacency unfolds to a boolean combination of decidable relations: inequality on Fin 7, adjacency in C_7, and nonemptiness of a finite intersection of finsets, so Lean's typeclass synthesis derives the Decidable instance.

    lines 11–13

    instance (u v : Fin 7) : Decidable (exists_triangle_free_all_powers_well_covered_diam_eq_three_c7_sq.Adj u v) := by
      dsimp [exists_triangle_free_all_powers_well_covered_diam_eq_three_c7_sq]
      infer_instance
  3. Two vertices in C_7 have intersecting neighbor finsets if and only if their common neighbors set is nonempty.

    A vertex lies in the intersection of the neighbor finsets of u and v if and only if it is adjacent to both, which by `SimpleGraph.mem_commonNeighbors` means it is a common neighbor.

    lines 15–18

    uses SimpleGraph.mem_commonNeighbors

    lemma exists_triangle_free_all_powers_well_covered_diam_eq_three_neighborFinset_inter_nonempty (u v : Fin 7) :
        ((SimpleGraph.cycleGraph 7).neighborFinset u ∩ (SimpleGraph.cycleGraph 7).neighborFinset v).Nonempty ↔
          ((SimpleGraph.cycleGraph 7).commonNeighbors u v).Nonempty := by
      simp [Finset.Nonempty, Set.Nonempty, SimpleGraph.mem_commonNeighbors]
  4. The graph power C_7^2 equals the explicit square graph exists_triangle_free_all_powers_well_covered_diam_eq_three_c7_sq.

    By extensionality, an edge in C_7^2 joins distinct vertices at distance at most 2. Using `SimpleGraph.two_lt_edist_iff`, distance strictly exceeds 2 if and only if the vertices are distinct, non-adjacent, and have no common neighbors; negating this via `not_lt` and `Set.nonempty_iff_ne_empty` shows that distance at most 2 is equivalent to adjacency in C_7 or having a common neighbor.

    lines 20–27

    uses exists_triangle_free_all_powers_well_covered_diam_eq_three_neighborFinset_inter_nonempty, not_lt, SimpleGraph.two_lt_edist_iff, Set.nonempty_iff_ne_empty

    lemma exists_triangle_free_all_powers_well_covered_diam_eq_three_c7_sq_eq :
        simple_graph_power (SimpleGraph.cycleGraph 7) 2 = exists_triangle_free_all_powers_well_covered_diam_eq_three_c7_sq := by
      ext u v
      dsimp [simple_graph_power, exists_triangle_free_all_powers_well_covered_diam_eq_three_c7_sq]
      rw [exists_triangle_free_all_powers_well_covered_diam_eq_three_neighborFinset_inter_nonempty]
      rw [← not_lt, SimpleGraph.two_lt_edist_iff, Set.nonempty_iff_ne_empty]
      tauto
    
  5. In C_7^2, every independent set has size at most 2, and any independent set of size strictly less than 2 can be extended by adding another vertex. automation

    After rewriting the graph power to the explicit square graph, both assertions are checked by exhaustive verification (`decide`) over all subsets of Fin 7.

    lines 28–33

    uses exists_triangle_free_all_powers_well_covered_diam_eq_three_c7_sq_eq

    lemma exists_triangle_free_all_powers_well_covered_diam_eq_three_c7_sq_wc :
        simple_graph_is_well_covered (simple_graph_power (SimpleGraph.cycleGraph 7) 2) := by
      rw [exists_triangle_free_all_powers_well_covered_diam_eq_three_c7_sq_eq]
      have test1 : ∀ (s : Finset (Fin 7)), exists_triangle_free_all_powers_well_covered_diam_eq_three_c7_sq.IsIndepSet ↑s → s.card ≤ 2 := by decide
      have test2 : ∀ (s : Finset (Fin 7)), exists_triangle_free_all_powers_well_covered_diam_eq_three_c7_sq.IsIndepSet ↑s → s.card < 2 →
          ∃ v ∉ s, exists_triangle_free_all_powers_well_covered_diam_eq_three_c7_sq.IsIndepSet ↑(insert v s) := by decide
  6. The square graph C_7^2 is well-covered.

    Any maximal independent set u has size at most 2. If |u| < 2, the previous step produces a vertex v ∉ u such that u ∪ {v} is independent, which contradicts the maximality of u; hence |u| = 2. Thus every maximal independent set has cardinality 2, so any two maximal independent sets have the same size.

    lines 34–46

    uses le_antisymm, lt_of_not_ge, Finset.subset_insert, Finset.mem_insert_self

      intro s t hs ht
      have hcard : ∀ u : Finset (Fin 7), Maximal (fun w : Finset (Fin 7) => exists_triangle_free_all_powers_well_covered_diam_eq_three_c7_sq.IsIndepSet (w : Set (Fin 7))) u → u.card = 2 := by
        intro u hu
        apply le_antisymm (test1 u hu.1)
        by_contra hlt
        have hlt' : u.card < 2 := lt_of_not_ge hlt
        obtain ⟨v, hv, hind⟩ := test2 u hu.1 hlt'
        have hsub : u ≤ insert v u := Finset.subset_insert v u
        have heq := hu.2 hind hsub
        have : v ∈ u := heq (Finset.mem_insert_self v u)
        exact hv this
      rw [hcard s hs, hcard t ht]
    
  7. In C_7, every independent set has size at most 3, and any independent set of size strictly less than 3 can be extended by adding another vertex. automation

    Both properties are verified by exhaustive computation (`decide`) over all subsets of Fin 7.

    lines 47–51

    lemma exists_triangle_free_all_powers_well_covered_diam_eq_three_c7_wc :
        simple_graph_is_well_covered (SimpleGraph.cycleGraph 7) := by
      have test1 : ∀ (s : Finset (Fin 7)), (SimpleGraph.cycleGraph 7).IsIndepSet ↑s → s.card ≤ 3 := by decide
      have test2 : ∀ (s : Finset (Fin 7)), (SimpleGraph.cycleGraph 7).IsIndepSet ↑s → s.card < 3 →
          ∃ v ∉ s, (SimpleGraph.cycleGraph 7).IsIndepSet ↑(insert v s) := by decide
  8. The cycle graph C_7 is well-covered.

    Every maximal independent set u has size at most 3. If |u| < 3, it could be extended by an additional vertex into a larger independent set, contradicting maximality; hence |u| = 3. Consequently, all maximal independent sets have cardinality 3.

    lines 52–64

    uses le_antisymm, lt_of_not_ge, Finset.subset_insert, Finset.mem_insert_self

      intro s t hs ht
      have hcard : ∀ u : Finset (Fin 7), Maximal (fun w : Finset (Fin 7) => (SimpleGraph.cycleGraph 7).IsIndepSet (w : Set (Fin 7))) u → u.card = 3 := by
        intro u hu
        apply le_antisymm (test1 u hu.1)
        by_contra hlt
        have hlt' : u.card < 3 := lt_of_not_ge hlt
        obtain ⟨v, hv, hind⟩ := test2 u hu.1 hlt'
        have hsub : u ≤ insert v u := Finset.subset_insert v u
        have heq := hu.2 hind hsub
        have : v ∈ u := heq (Finset.mem_insert_self v u)
        exact hv this
      rw [hcard s hs, hcard t ht]
    
  9. The existential statement is instantiated with the cycle graph C_7 on vertices Fin 7.

    The witness graph G is chosen to be SimpleGraph.cycleGraph 7 on vertex type Fin 7, generating subgoals for connectedness, triangle-freeness, vertex count at least 2, diameter equal to 3, and well-coveredness of all powers.

    line 73

      refine ⟨Fin 7, inferInstance, SimpleGraph.cycleGraph 7, ?_, ?_, ?_, ?_, ?_⟩
  10. C_7 is connected.

    This is immediate from `SimpleGraph.cycleGraph_connected`, which proves that cycle graphs C_{n+1} are connected.

    line 74

    uses SimpleGraph.cycleGraph_connected

      · exact SimpleGraph.cycleGraph_connected (n := 6)
  11. C_7 is triangle-free (contains no 3-cliques). automation

    Given any potential 3-clique, finite decision procedure (`decide`) verifies that no 3-element subset of vertices forms a clique in C_7.

    lines 75–77

      · intro t ht
        have : ∀ s : Finset (Fin 7), s.card = 3 → ¬ (SimpleGraph.cycleGraph 7).IsClique ↑s := by decide
        exact this t ht.card_eq ht.isClique
  12. C_7 has at least two vertices. automation

    The vertex set Fin 7 has cardinality 7, and 2 ≤ 7 is closed by evaluation (`decide`).

    line 78

      · decide
  13. The diameter of C_7 is exactly 3.

    This is provided by the lemma `cycle_seven_diam_eq_three`.

    line 79

    uses cycle_seven_diam_eq_three

      · exact cycle_seven_diam_eq_three
  14. Every positive integer power C_7^d (for d ≥ 1) is well-covered.

    By `forall_power_well_covered_of_well_covered_diam_le_three`, any connected graph with diameter at most 3 whose base graph and square are both well-covered has all powers well-covered. This is applied using the connectedness of C_7, the diameter bound 3 ≤ 3, and the well-coveredness lemmas for C_7 and C_7^2.

    lines 80–85

    uses forall_power_well_covered_of_well_covered_diam_le_three, SimpleGraph.cycleGraph_connected, le_of_eq, cycle_seven_diam_eq_three, exists_triangle_free_all_powers_well_covered_diam_eq_three_c7_wc, exists_triangle_free_all_powers_well_covered_diam_eq_three_c7_sq_wc

      · exact forall_power_well_covered_of_well_covered_diam_le_three
          (SimpleGraph.cycleGraph 7)
          (SimpleGraph.cycleGraph_connected (n := 6))
          (le_of_eq cycle_seven_diam_eq_three)
          exists_triangle_free_all_powers_well_covered_diam_eq_three_c7_wc
          exists_triangle_free_all_powers_well_covered_diam_eq_three_c7_sq_wc
Finset.inter_comm
Intersection of finite sets is commutative: s₁ ∩ s₂ = s₂ ∩ s₁.
SimpleGraph.mem_commonNeighbors
A vertex belongs to the set of common neighbors of two vertices if and only if it is adjacent to both.
exists_triangle_free_all_powers_well_covered_diam_eq_three_neighborFinset_inter_nonempty
In the cycle graph C_7, two vertices have an intersection in their neighbor finsets if and only if their common neighbors set is nonempty.
not_lt
In a linear order, ¬(a < b) is equivalent to b ≤ a.
SimpleGraph.two_lt_edist_iff
In a simple graph, the distance between u and v exceeds 2 if and only if u ≠ v, u and v are not adjacent, and they share no common neighbors.
Set.nonempty_iff_ne_empty
A set is nonempty if and only if it is distinct from the empty set.
exists_triangle_free_all_powers_well_covered_diam_eq_three_c7_sq_eq
The second graph power C_7^2 is definitionally equal to the explicit simple graph exists_triangle_free_all_powers_well_covered_diam_eq_three_c7_sq.
le_antisymm
In a partial order, a ≤ b and b ≤ a imply a = b.
lt_of_not_ge
In a linear order, ¬(b ≤ a) implies a < b.
Finset.subset_insert
A finite set s is a subset of {a} ∪ s.
Finset.mem_insert_self
An element a is an element of {a} ∪ s.
SimpleGraph.cycleGraph_connected
Every cycle graph C_{n+1} is connected.
cycle_seven_diam_eq_three
The diameter of the 7-cycle C_7 is equal to 3.
le_of_eq
An equality a = b in a preorder implies the inequality a ≤ b.
exists_triangle_free_all_powers_well_covered_diam_eq_three_c7_wc
The 7-cycle graph C_7 is well-covered.
exists_triangle_free_all_powers_well_covered_diam_eq_three_c7_sq_wc
The square of the 7-cycle graph C_7^2 is well-covered.
forall_power_well_covered_of_well_covered_diam_le_three
If a connected graph has diameter at most 3 and both the graph and its square are well-covered, then all of its powers G^d (for d ≥ 1) are well-covered.

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

def exists_triangle_free_all_powers_well_covered_diam_eq_three_c7_sq : SimpleGraph (Fin 7) where  Adj u v := u ≠ v ∧ ((SimpleGraph.cycleGraph 7).Adj u v ∨ ((SimpleGraph.cycleGraph 7).neighborFinset u ∩ (SimpleGraph.cycleGraph 7).neighborFinset v).Nonempty)  symm := ⟨by    intro u v h    refine ⟨h.1.symm, ?_⟩    rcases h.2 with h1 | h2    · left; exact h1.symm    · right; rw [Finset.inter_comm]; exact h2⟩  loopless := ⟨by intro u h; exact h.1 rfl⟩instance (u v : Fin 7) : Decidable (exists_triangle_free_all_powers_well_covered_diam_eq_three_c7_sq.Adj u v) := by  dsimp [exists_triangle_free_all_powers_well_covered_diam_eq_three_c7_sq]  infer_instancelemma exists_triangle_free_all_powers_well_covered_diam_eq_three_neighborFinset_inter_nonempty (u v : Fin 7) :    ((SimpleGraph.cycleGraph 7).neighborFinset u ∩ (SimpleGraph.cycleGraph 7).neighborFinset v).Nonempty ↔      ((SimpleGraph.cycleGraph 7).commonNeighbors u v).Nonempty := by  simp [Finset.Nonempty, Set.Nonempty, SimpleGraph.mem_commonNeighbors]lemma exists_triangle_free_all_powers_well_covered_diam_eq_three_c7_sq_eq :    simple_graph_power (SimpleGraph.cycleGraph 7) 2 = exists_triangle_free_all_powers_well_covered_diam_eq_three_c7_sq := by  ext u v  dsimp [simple_graph_power, exists_triangle_free_all_powers_well_covered_diam_eq_three_c7_sq]  rw [exists_triangle_free_all_powers_well_covered_diam_eq_three_neighborFinset_inter_nonempty]  rw [← not_lt, SimpleGraph.two_lt_edist_iff, Set.nonempty_iff_ne_empty]  tautolemma exists_triangle_free_all_powers_well_covered_diam_eq_three_c7_sq_wc :    simple_graph_is_well_covered (simple_graph_power (SimpleGraph.cycleGraph 7) 2) := by  rw [exists_triangle_free_all_powers_well_covered_diam_eq_three_c7_sq_eq]  have test1 : ∀ (s : Finset (Fin 7)), exists_triangle_free_all_powers_well_covered_diam_eq_three_c7_sq.IsIndepSet ↑s → s.card ≤ 2 := by decide  have test2 : ∀ (s : Finset (Fin 7)), exists_triangle_free_all_powers_well_covered_diam_eq_three_c7_sq.IsIndepSet ↑s → s.card < 2 →      ∃ v ∉ s, exists_triangle_free_all_powers_well_covered_diam_eq_three_c7_sq.IsIndepSet ↑(insert v s) := by decide  intro s t hs ht  have hcard : ∀ u : Finset (Fin 7), Maximal (fun w : Finset (Fin 7) => exists_triangle_free_all_powers_well_covered_diam_eq_three_c7_sq.IsIndepSet (w : Set (Fin 7))) u → u.card = 2 := by    intro u hu    apply le_antisymm (test1 u hu.1)    by_contra hlt    have hlt' : u.card < 2 := lt_of_not_ge hlt    obtain ⟨v, hv, hind⟩ := test2 u hu.1 hlt'    have hsub : u ≤ insert v u := Finset.subset_insert v u    have heq := hu.2 hind hsub    have : v ∈ u := heq (Finset.mem_insert_self v u)    exact hv this  rw [hcard s hs, hcard t ht]lemma exists_triangle_free_all_powers_well_covered_diam_eq_three_c7_wc :    simple_graph_is_well_covered (SimpleGraph.cycleGraph 7) := by  have test1 : ∀ (s : Finset (Fin 7)), (SimpleGraph.cycleGraph 7).IsIndepSet ↑s → s.card ≤ 3 := by decide  have test2 : ∀ (s : Finset (Fin 7)), (SimpleGraph.cycleGraph 7).IsIndepSet ↑s → s.card < 3 →      ∃ v ∉ s, (SimpleGraph.cycleGraph 7).IsIndepSet ↑(insert v s) := by decide  intro s t hs ht  have hcard : ∀ u : Finset (Fin 7), Maximal (fun w : Finset (Fin 7) => (SimpleGraph.cycleGraph 7).IsIndepSet (w : Set (Fin 7))) u → u.card = 3 := by    intro u hu    apply le_antisymm (test1 u hu.1)    by_contra hlt    have hlt' : u.card < 3 := lt_of_not_ge hlt    obtain ⟨v, hv, hind⟩ := test2 u hu.1 hlt'    have hsub : u ≤ insert v u := Finset.subset_insert v u    have heq := hu.2 hind hsub    have : v ∈ u := heq (Finset.mem_insert_self v u)    exact hv this  rw [hcard s hs, hcard t ht]/-- The diameter-3 bound for triangle-free graphs whose powers are all well-covered is sharp (witnessed by C_7). -/theorem exists_triangle_free_all_powers_well_covered_diam_eq_three :    ∃ (V : Type) (_ : Fintype V) (G : SimpleGraph V),      G.Connected ∧      G.CliqueFree 3 ∧      2 ≤ Fintype.card V ∧      G.diam = 3 ∧      (∀ d : ℕ, 1 ≤ d → simple_graph_is_well_covered (simple_graph_power G d)) := by  refine ⟨Fin 7, inferInstance, SimpleGraph.cycleGraph 7, ?_, ?_, ?_, ?_, ?_⟩  · exact SimpleGraph.cycleGraph_connected (n := 6)  · intro t ht    have : ∀ s : Finset (Fin 7), s.card = 3 → ¬ (SimpleGraph.cycleGraph 7).IsClique ↑s := by decide    exact this t ht.card_eq ht.isClique  · decide  · exact cycle_seven_diam_eq_three  · exact forall_power_well_covered_of_well_covered_diam_le_three      (SimpleGraph.cycleGraph 7)      (SimpleGraph.cycleGraph_connected (n := 6))      (le_of_eq cycle_seven_diam_eq_three)      exists_triangle_free_all_powers_well_covered_diam_eq_three_c7_wc      exists_triangle_free_all_powers_well_covered_diam_eq_three_c7_sq_wc
See it in the graphDiscuss this resultChallenge it