exists_connected_all_powers_well_covered_diam_ge
For every positive integer D, there exists a finite connected simple graph G with diameter at least D such that every positive power G^d (d ≥ 1) is well-covered.
Statement
theorem exists_connected_all_powers_well_covered_diam_ge (D : ℕ) (hD : 0 < D) : ∃ (V : Type) (_ : Fintype V) (G : SimpleGraph V), G.Connected ∧ D ≤ G.diam ∧ ∀ d : ℕ, 1 ≤ d → simple_graph_is_well_covered (simple_graph_power G d)
- Formalizes
- arXiv:2611.03956 Corollary 2.13
- Verified
- 05 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- complete_graph_two_all_powers_well_coveredThe complete graph on 2 vertices K_2 is connected, has diameter 1, and every positive power K_2^d (d ≥ 1) is well-covered.
- diam_boxProd_completeGraphFor every finite connected graph G on a nonempty vertex set and every integer t ≥ 2, the diameter of the Cartesian product G □ K_t is…
- boxProd_completeGraph_all_powers_well_coveredLet G be a finite connected nontrivial graph, and let t be an integer with t > |V(G)|. If every positive power G^d (d ≥ 1) is…
- 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…
- 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…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
Read back from the Lean
For every positive integer $D$, there exists a finite type $V$ and a simple graph $G$ on $V$ such that: 1. $G$ is connected; 2. the diameter of $G$ is at least $D$ ($D \le G.\mathrm{diam}$); and 3. for every integer $d \ge 1$, the $d$-th power of $G$ is well-covered (meaning all maximal independent sets in the $d$-th power of $G$ have the same cardinality).
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 proved by strengthening the goal to show by induction on $n \ge 1$ that there exists a connected graph $G$ on at least 2 vertices with diameter at least $n$ whose positive powers $G^d$ ($d \ge 1$) are all well-covered. The base case $n = 1$ is satisfied by the complete graph $K_2$. In the inductive step, given a suitable graph $G$ with diameter at least $k+1$, taking its Cartesian product with a sufficiently large complete graph $K_t$ (where $t = |V(G)| + 2$) increases the diameter by 1 to at least $k+2$ while preserving connectedness, non-triviality, and well-coveredness of all powers. Specialising this result to $n = D$ completes the proof.
We formulate a strengthened claim by induction on $n \ge 1$: there exists a connected graph on at least 2 vertices with diameter at least $n$ whose positive powers are all well-covered. The case $n=0$ is discharged vacuously.
We introduce the auxiliary lemma `strong`, strengthening the statement by requiring $2 \le |V(G)|$, and induct on $n$. The base case $n=0$ is dismissed immediately because the hypothesis $1 \le 0$ is contradictory by linear arithmetic (`omega`).
have strong : ∀ n : ℕ, 1 ≤ n → ∃ (V : Type) (_ : Fintype V) (G : SimpleGraph V), 2 ≤ Fintype.card V ∧ G.Connected ∧ n ≤ G.diam ∧ ∀ d : ℕ, 1 ≤ d → simple_graph_is_well_covered (simple_graph_power G d) := by intro n hn induction n with | zero => omega
The base case $n = 1$ holds using the complete graph on two vertices $K_2$.
Splitting $n+1$ at $n=0$ isolates the case $n=1$. We instantiate the witness with $K_2$ on the vertex set $\operatorname{Fin} 2$. Its vertex count is 2 (by `simp`), and `complete_graph_two_all_powers_well_covered` provides that $K_2$ is connected, has diameter $1 \ge 1$, and has well-covered powers for all $d \ge 1$.
uses
complete_graph_two_all_powers_well_covered.1,complete_graph_two_all_powers_well_covered.2.1,complete_graph_two_all_powers_well_covered.2.2| succ n ih => cases n with | zero => refine ⟨Fin 2, inferInstance, SimpleGraph.completeGraph (Fin 2), ?_, ?_, ?_, ?_⟩ · simp · exact complete_graph_two_all_powers_well_covered.1 · rw [complete_graph_two_all_powers_well_covered.2.1] · exact complete_graph_two_all_powers_well_covered.2.2In the inductive step for $k+2$, we obtain a graph $G$ for $k+1$ from the induction hypothesis and construct an auxiliary complete graph $K_t$ with $t = |V(G)| + 2$.
Applying the induction hypothesis to $k+1 \ge 1$ yields a connected graph $G$ on $V$ with $|V| \ge 2$, $\operatorname{diam}(G) \ge k+1$, and well-covered powers. Since $G$ is connected, $V$ is nonempty. Setting $t = |V| + 2$ ensures $t > |V|$ and $t \ge 2$. Then $\operatorname{Fin} t$ is nonempty because $t > 0$ (`Fintype.card_pos_iff`), which implies that the complete graph $K_t$ (identical to $\top$ by `SimpleGraph.completeGraph_eq_top`) is connected by `SimpleGraph.connected_top`.
uses
Fintype.card_pos_iff,SimpleGraph.completeGraph_eq_top,SimpleGraph.connected_top| succ k => have hk : 1 ≤ Nat.succ k := by omega obtain ⟨V, instV, G, hcard, hconn, hdiam, hwc⟩ := ih hk letI := instV haveI : Nonempty V := hconn.nonempty let t := Fintype.card V + 2 have ht_gt : Fintype.card V < t := by dsimp [t]; omega have ht2 : 2 ≤ t := by dsimp [t]; omega haveI : Nonempty (Fin t) := by rw [← Fintype.card_pos_iff] simp [t] have hcomp : (SimpleGraph.completeGraph (Fin t)).Connected := by rw [SimpleGraph.completeGraph_eq_top] exact SimpleGraph.connected_topThe Cartesian product $G \mathbin{\square} K_t$ satisfies the four required conditions for $k+2$.
We propose $G \mathbin{\square} K_t$ on vertex set $V \times \operatorname{Fin} t$. The number of vertices is $|V| \cdot t \ge 2$ by `Fintype.card_prod`, `Fintype.card_fin`, and nonlinear arithmetic (`nlinarith`). The product of two connected graphs is connected (`SimpleGraph.Connected.boxProd`). By `diam_boxProd_completeGraph`, the diameter increases to $\operatorname{diam}(G) + 1 \ge (k+1) + 1 = k+2$. Finally, since $t > |V|$, $|V| \ge 2$, and all powers of $G$ are well-covered, `boxProd_completeGraph_all_powers_well_covered` proves that every positive power of $G \mathbin{\square} K_t$ is well-covered.
uses
Fintype.card_prod,Fintype.card_fin,SimpleGraph.Connected.boxProd,diam_boxProd_completeGraph,boxProd_completeGraph_all_powers_well_coveredrefine ⟨V × Fin t, inferInstance, G □ SimpleGraph.completeGraph (Fin t), ?_, ?_, ?_, ?_⟩ · rw [Fintype.card_prod, Fintype.card_fin] have : 1 ≤ Fintype.card V := by omega nlinarith · exact SimpleGraph.Connected.boxProd hconn hcomp · rw [diam_boxProd_completeGraph G hconn t ht2] omega · intro d hd exact boxProd_completeGraph_all_powers_well_covered G hconn hcard hwc t ht_gt d hd
The main theorem follows by applying the strengthened lemma to $D$.
Since $0 < D$, that is $1 \le D$, we specialise `strong` to $D$ to obtain a connected graph $G$ with diameter at least $D$ whose positive powers are all well-covered.
obtain ⟨V, instV, G, hcard, hconn, hdiam, hwc⟩ := strong D hD exact ⟨V, instV, G, hconn, hdiam, hwc⟩
complete_graph_two_all_powers_well_covered.1- The complete graph on two vertices $K_2$ is connected.
complete_graph_two_all_powers_well_covered.2.1- The diameter of the complete graph on two vertices $K_2$ is equal to 1.
complete_graph_two_all_powers_well_covered.2.2- For every integer $d \ge 1$, the $d$-th power of the complete graph on two vertices $K_2$ is well-covered.
Fintype.card_pos_iff- A finite type is nonempty if and only if its cardinality is strictly positive.
SimpleGraph.completeGraph_eq_top- The complete graph on a vertex set $V$ is equal to the top graph $\top$ on $V$.
SimpleGraph.connected_top- The complete graph on any nonempty vertex set is connected.
Fintype.card_prod- The cardinality of the Cartesian product of two finite types is the product of their cardinalities.
Fintype.card_fin- The cardinality of the finite type $\operatorname{Fin} n$ is $n$.
SimpleGraph.Connected.boxProd- The Cartesian product of two connected graphs is connected.
diam_boxProd_completeGraph- The diameter of the Cartesian product of a connected graph $G$ with a complete graph $K_t$ (for $t \ge 2$) equals $\operatorname{diam}(G) + 1$.
boxProd_completeGraph_all_powers_well_covered- If $G$ is a connected graph with at least 2 vertices whose positive powers are all well-covered, and $t > |V(G)|$, then every positive power of $G \mathbin{\square} K_t$ is also well-covered.
- The proof strengthens the induction hypothesis to require $|V(G)| \ge 2$, which is needed to apply `boxProd_completeGraph_all_powers_well_covered` in the inductive step.
- The Cartesian product (box product) of graphs $G$ and $H$ is denoted in Lean by $G \mathbin{\square} H$.
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.
/-- Existence of connected graphs with well-covered powers of arbitrarily large diameter. -/theorem exists_connected_all_powers_well_covered_diam_ge (D : ℕ) (hD : 0 < D) : ∃ (V : Type) (_ : Fintype V) (G : SimpleGraph V), G.Connected ∧ D ≤ G.diam ∧ ∀ d : ℕ, 1 ≤ d → simple_graph_is_well_covered (simple_graph_power G d) := by have strong : ∀ n : ℕ, 1 ≤ n → ∃ (V : Type) (_ : Fintype V) (G : SimpleGraph V), 2 ≤ Fintype.card V ∧ G.Connected ∧ n ≤ G.diam ∧ ∀ d : ℕ, 1 ≤ d → simple_graph_is_well_covered (simple_graph_power G d) := by intro n hn induction n with | zero => omega | succ n ih => cases n with | zero => refine ⟨Fin 2, inferInstance, SimpleGraph.completeGraph (Fin 2), ?_, ?_, ?_, ?_⟩ · simp · exact complete_graph_two_all_powers_well_covered.1 · rw [complete_graph_two_all_powers_well_covered.2.1] · exact complete_graph_two_all_powers_well_covered.2.2 | succ k => have hk : 1 ≤ Nat.succ k := by omega obtain ⟨V, instV, G, hcard, hconn, hdiam, hwc⟩ := ih hk letI := instV haveI : Nonempty V := hconn.nonempty let t := Fintype.card V + 2 have ht_gt : Fintype.card V < t := by dsimp [t]; omega have ht2 : 2 ≤ t := by dsimp [t]; omega haveI : Nonempty (Fin t) := by rw [← Fintype.card_pos_iff] simp [t] have hcomp : (SimpleGraph.completeGraph (Fin t)).Connected := by rw [SimpleGraph.completeGraph_eq_top] exact SimpleGraph.connected_top refine ⟨V × Fin t, inferInstance, G □ SimpleGraph.completeGraph (Fin t), ?_, ?_, ?_, ?_⟩ · rw [Fintype.card_prod, Fintype.card_fin] have : 1 ≤ Fintype.card V := by omega nlinarith · exact SimpleGraph.Connected.boxProd hconn hcomp · rw [diam_boxProd_completeGraph G hconn t ht2] omega · intro d hd exact boxProd_completeGraph_all_powers_well_covered G hconn hcard hwc t ht_gt d hd obtain ⟨V, instV, G, hcard, hconn, hdiam, hwc⟩ := strong D hD exact ⟨V, instV, G, hconn, hdiam, hwc⟩