AFTD Auto-Formalizing Theoretical Domains

exists_connected_all_powers_well_covered_diam_ge

theoremverifiedformalization

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 than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.

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.

  1. 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`).

    lines 7–12

      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
  2. 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$.

    lines 13–20

    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.2
  3. In 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`.

    lines 21–34

    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_top
  4. The 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.

    lines 35–43

    uses Fintype.card_prod, Fintype.card_fin, SimpleGraph.Connected.boxProd, diam_boxProd_completeGraph, boxProd_completeGraph_all_powers_well_covered

            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
  5. 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.

    lines 44–45

      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.

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

/-- 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⟩
See it in the graphDiscuss this resultChallenge it