exists_triangle_free_all_powers_well_covered_diam_eq_three
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
- simple_graph_powerThe d-th power G^d of a graph G: same vertices, two distinct vertices adjacent iff they are joined by a path (equivalently a walk) of…
- forall_power_well_covered_of_well_covered_diam_le_threeLet G be a finite connected simple graph of diameter at most 3. If G and its second power G^2 are both well-covered, then every positive…
- cycle_seven_diam_eq_threeThe diameter of the 7-cycle graph C_7 is equal to 3.
- simple_graph_is_well_coveredA finite graph is well-covered if all its maximal independent sets have the same cardinality (equivalently, all its minimal vertex covers…
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.
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.
uses
Finset.inter_commsymm := ⟨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⟩
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.
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
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.
uses
SimpleGraph.mem_commonNeighborslemma 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]
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.
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_emptylemma 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
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.
uses
exists_triangle_free_all_powers_well_covered_diam_eq_three_c7_sq_eqlemma 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
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.
uses
le_antisymm,lt_of_not_ge,Finset.subset_insert,Finset.mem_insert_selfintro 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]
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.
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
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.
uses
le_antisymm,lt_of_not_ge,Finset.subset_insert,Finset.mem_insert_selfintro 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 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.
refine ⟨Fin 7, inferInstance, SimpleGraph.cycleGraph 7, ?_, ?_, ?_, ?_, ?_⟩C_7 is connected.
This is immediate from `SimpleGraph.cycleGraph_connected`, which proves that cycle graphs C_{n+1} are connected.
uses
SimpleGraph.cycleGraph_connected· exact SimpleGraph.cycleGraph_connected (n := 6)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.
· 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
C_7 has at least two vertices. automation
The vertex set Fin 7 has cardinality 7, and 2 ≤ 7 is closed by evaluation (`decide`).
· decideThe diameter of C_7 is exactly 3.
This is provided by the lemma `cycle_seven_diam_eq_three`.
uses
cycle_seven_diam_eq_three· exact cycle_seven_diam_eq_threeEvery 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.
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.
- The independence number bounds, independent set extensibility, and absence of 3-cliques in C_7 and its square are proved via exhaustive finite enumeration using the `decide` tactic over the power set of Fin 7.
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.
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