AFTD Auto-Formalizing Theoretical Domains

forall_power_well_covered_of_well_covered_diam_le_three

theoremverified

Let 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 integer power G^d (for d ≥ 1) is well-covered.

Statement

theorem forall_power_well_covered_of_well_covered_diam_le_three {V : Type*} [Fintype V]
    (G : SimpleGraph V) (hconn : G.Connected) (hdiam : G.diam ≤ 3)
    (hwc1 : simple_graph_is_well_covered G)
    (hwc2 : simple_graph_is_well_covered (simple_graph_power G 2)) :
    ∀ d : ℕ, 1 ≤ d → simple_graph_is_well_covered (simple_graph_power G d)
Source
arXiv:2610.09300; OP-537
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 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…
  • 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_power_oneG^1 = G.
Used by 1

Read back from the Lean

Let $V$ be a finite type, and let $G$ be a simple graph on $V$. Assume that: 1. $G$ is connected (G.Connected), 2. The diameter of $G$ is at most 3 (G.diam ≤ 3), 3. $G$ is well-covered (simple_graph_is_well_covered G), and 4. The second power graph of $G$, $G^2$ (simple_graph_power G 2), is well-covered. Then for every natural number $d \ge 1$, the $d$-th power graph $G^d$ (simple_graph_power G d) 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

To show that every power Gᵈ (for d ≥ 1) of a connected graph G with diameter at most 3 is well-covered, the argument splits into cases on the exponent d. For d = 1 and d = 2, well-coveredness holds by assumption since G¹ = G. For d ≥ 3, any two distinct vertices in G are at distance at most diam(G) ≤ 3 ≤ d, so the power graph Gᵈ coincides with the complete graph. Finally, the complete graph is shown to be well-covered because its maximal independent sets are precisely the singletons, which concludes the proof.

  1. A finite subset of vertices is an independent set in the complete graph if and only if its cardinality is at most 1.

    In the complete graph ⊤, every pair of distinct vertices is adjacent. An independent set cannot contain two distinct vertices, so any two elements in it must be equal; by Finset.card_le_one, this is equivalent to having cardinality at most 1. Conversely, if a set has at most one element, it contains no pairs of distinct vertices, so no two vertices in it are adjacent, making it independent.

    lines 4–13

    uses Finset.card_le_one

      constructor
      · intro h
        rw [Finset.card_le_one]
        intro a ha b hb
        by_contra hab
        exact (h ha hb hab) hab
      · intro h
        rw [Finset.card_le_one] at h
        intro a ha b hb hab
        exact fun hne => hne (h a ha b hb)
  2. In the complete graph on a nonempty vertex set, every maximal independent set has cardinality 1.

    By forall_power_well_covered_of_well_covered_diam_le_three_aux_indep_top_iff, any independent set s satisfies |s| ≤ 1. If s were empty, choosing any vertex v from the nonempty vertex set would yield a singleton {v}, which is independent and strictly contains ∅ = s (via Finset.empty_subset), contradicting the maximality of s. Hence s is nonempty (Finset.card_pos, Finset.not_nonempty_iff_eq_empty), giving |s| > 0. Together with |s| ≤ 1, this forces |s| = 1.

    lines 19–33

    uses forall_power_well_covered_of_well_covered_diam_le_three_aux_indep_top_iff, Finset.card_pos, Finset.not_nonempty_iff_eq_empty, Finset.empty_subset

      have hle : s.card ≤ 1 :=
        forall_power_well_covered_of_well_covered_diam_le_three_aux_indep_top_iff s |>.mp hs.1
      have hpos : 0 < s.card := by
        rw [Finset.card_pos]
        by_contra hne
        rw [Finset.not_nonempty_iff_eq_empty] at hne
        obtain ⟨v⟩ := ‹Nonempty V›
        have ht : (⊤ : SimpleGraph V).IsIndepSet (↑({v} : Finset V)) := by
          rw [forall_power_well_covered_of_well_covered_diam_le_three_aux_indep_top_iff]; simp
        have hsub : s ≤ ({v} : Finset V) := by rw [hne]; exact Finset.empty_subset _
        have hle2 : ({v} : Finset V) ≤ s := hs.2 ht hsub
        have hv : v ∈ s := hle2 (by simp)
        rw [hne] at hv
        simp at hv
      omega
  3. The complete graph on a finite nonempty vertex set is well-covered.

    A graph is well-covered if all its maximal independent sets have the same cardinality. For the complete graph, any two maximal independent sets s and t each have cardinality 1 by forall_power_well_covered_of_well_covered_diam_le_three_aux_top_card_eq_one, so |s| = |t|.

    lines 38–40

    uses forall_power_well_covered_of_well_covered_diam_le_three_aux_top_card_eq_one

      intro s t hs ht
      rw [forall_power_well_covered_of_well_covered_diam_le_three_aux_top_card_eq_one s hs,
        forall_power_well_covered_of_well_covered_diam_le_three_aux_top_card_eq_one t ht]
  4. The vertex set of G is nonempty and the extended diameter of G is finite.

    Because G is connected, its vertex set contains at least one vertex, and its extended diameter is finite (SimpleGraph.connected_iff_ediam_ne_top.mp).

    lines 48–49

    uses SimpleGraph.connected_iff_ediam_ne_top.mp

      haveI : Nonempty V := hconn.nonempty
      have hne_ediam : G.ediam ≠ ⊤ := SimpleGraph.connected_iff_ediam_ne_top.mp hconn
  5. For every integer d ≥ 3, the graph power Gᵈ is the complete graph.

    Two distinct vertices u and v are adjacent in Gᵈ if their distance in G is at most d. Since G is connected, u and v are reachable, so their distance is finite (SimpleGraph.edist_ne_top_iff_reachable.mpr). The distance between u and v is bounded by the graph diameter (SimpleGraph.edist_le_ediam, ENat.toNat_le_toNat), which is at most 3 by hypothesis. Since 3 ≤ d, transitivity (le_trans) gives dist_G(u, v) ≤ d. Thus all pairs of distinct vertices are adjacent in Gᵈ, showing Gᵈ = ⊤.

    lines 50–65

    uses SimpleGraph.edist_ne_top_iff_reachable.mpr, ENat.toNat_le_toNat, SimpleGraph.edist_le_ediam, ENat.natCast_toNat_eq_self.mpr, le_trans

      have htop : ∀ d : ℕ, 3 ≤ d → simple_graph_power G d = ⊤ := by
        intro d hd
        ext u v
        constructor
        · intro h; exact h.1
        · intro huv
          refine ⟨huv, ?_⟩
          have hreach : G.Reachable u v := hconn u v
          have hne : G.edist u v ≠ ⊤ := SimpleGraph.edist_ne_top_iff_reachable.mpr hreach
          have htoNat : (G.edist u v).toNat ≤ G.diam :=
            ENat.toNat_le_toNat SimpleGraph.edist_le_ediam hne_ediam
          have heq : G.edist u v = ((G.edist u v).toNat : ℕ∞) :=
            (ENat.natCast_toNat_eq_self.mpr hne).symm
          rw [heq]
          have hle : (G.edist u v).toNat ≤ d := le_trans htoNat (le_trans hdiam hd)
          exact_mod_cast hle
  6. The graph power Gᵈ is well-covered when d = 1 or d = 2, and the case d = 0 is ruled out.

    We perform case analysis on d. The case d = 0 contradicts the hypothesis 1 ≤ d and is closed by linear arithmetic. For d = 1, the power graph G¹ equals G by simple_graph_power_one, which is well-covered by hypothesis. For d = 2, G² is well-covered directly by hypothesis.

    lines 66–70

    uses simple_graph_power_one

      intro d hd
      rcases d with _ | _ | _ | k
      · omega
      · rw [simple_graph_power_one]; exact hwc1
      · exact hwc2
  7. For every d ≥ 3, the graph power Gᵈ is well-covered.

    For d ≥ 3, writing d = k + 3, the power graph Gᵏ⁺³ equals the complete graph ⊤. Because the complete graph on a finite nonempty vertex set is well-covered (forall_power_well_covered_of_well_covered_diam_le_three_aux_top), Gᵈ is well-covered.

    lines 71–73

    uses forall_power_well_covered_of_well_covered_diam_le_three_aux_top

      · have htopd : simple_graph_power G (k + 3) = ⊤ := htop (k + 3) (by omega)
        rw [htopd]
        exact forall_power_well_covered_of_well_covered_diam_le_three_aux_top
Finset.card_le_one
A finite set has cardinality at most 1 if and only if any two of its elements are equal.
forall_power_well_covered_of_well_covered_diam_le_three_aux_indep_top_iff
A finite subset of vertices is an independent set in the complete graph if and only if its cardinality is at most 1.
Finset.card_pos
A finite set has strictly positive cardinality if and only if it is nonempty.
Finset.not_nonempty_iff_eq_empty
A finite set is not nonempty if and only if it is equal to the empty set.
Finset.empty_subset
The empty set is a subset of any finite set.
forall_power_well_covered_of_well_covered_diam_le_three_aux_top_card_eq_one
In the complete graph on a nonempty vertex set, every maximal independent set has cardinality 1.
forall_power_well_covered_of_well_covered_diam_le_three_aux_top
The complete graph on a finite nonempty vertex set is well-covered.
SimpleGraph.connected_iff_ediam_ne_top.mp
If a graph is connected, its extended diameter is not infinite.
SimpleGraph.edist_ne_top_iff_reachable.mpr
If two vertices are reachable from one another in a graph, their extended distance is not infinite.
SimpleGraph.edist_le_ediam
The extended distance between any two vertices in a graph is at most the extended diameter of the graph.
ENat.toNat_le_toNat
If an extended natural number m is at most an extended natural number n, and n is finite, then the natural number conversion of m is at most that of n.
ENat.natCast_toNat_eq_self.mpr
If an extended natural number is not infinite, embedding its natural number conversion back into the extended natural numbers yields the original value.
le_trans
Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
simple_graph_power_one
The first power of a graph G¹ is equal to G.

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

private lemma forall_power_well_covered_of_well_covered_diam_le_three_aux_indep_top_iff    {V : Type*} (s : Finset V) :    (⊤ : SimpleGraph V).IsIndepSet (↑s) ↔ s.card ≤ 1 := by  constructor  · intro h    rw [Finset.card_le_one]    intro a ha b hb    by_contra hab    exact (h ha hb hab) hab  · intro h    rw [Finset.card_le_one] at h    intro a ha b hb hab    exact fun hne => hne (h a ha b hb)private lemma forall_power_well_covered_of_well_covered_diam_le_three_aux_top_card_eq_one    {V : Type*} [Nonempty V] (s : Finset V)    (hs : Maximal (fun u : Finset V => (⊤ : SimpleGraph V).IsIndepSet (↑u)) s) :    s.card = 1 := by  have hle : s.card ≤ 1 :=    forall_power_well_covered_of_well_covered_diam_le_three_aux_indep_top_iff s |>.mp hs.1  have hpos : 0 < s.card := by    rw [Finset.card_pos]    by_contra hne    rw [Finset.not_nonempty_iff_eq_empty] at hne    obtain ⟨v⟩ := ‹Nonempty V›    have ht : (⊤ : SimpleGraph V).IsIndepSet (↑({v} : Finset V)) := by      rw [forall_power_well_covered_of_well_covered_diam_le_three_aux_indep_top_iff]; simp    have hsub : s ≤ ({v} : Finset V) := by rw [hne]; exact Finset.empty_subset _    have hle2 : ({v} : Finset V) ≤ s := hs.2 ht hsub    have hv : v ∈ s := hle2 (by simp)    rw [hne] at hv    simp at hv  omegaprivate lemma forall_power_well_covered_of_well_covered_diam_le_three_aux_top    {V : Type*} [Fintype V] [Nonempty V] :    simple_graph_is_well_covered (⊤ : SimpleGraph V) := by  intro s t hs ht  rw [forall_power_well_covered_of_well_covered_diam_le_three_aux_top_card_eq_one s hs,    forall_power_well_covered_of_well_covered_diam_le_three_aux_top_card_eq_one t ht]/-- A connected graph of diameter at most 3 has all powers well-covered if G and G^2 are well-covered. -/theorem forall_power_well_covered_of_well_covered_diam_le_three {V : Type*} [Fintype V]    (G : SimpleGraph V) (hconn : G.Connected) (hdiam : G.diam ≤ 3)    (hwc1 : simple_graph_is_well_covered G)    (hwc2 : simple_graph_is_well_covered (simple_graph_power G 2)) :    ∀ d : ℕ, 1 ≤ d → simple_graph_is_well_covered (simple_graph_power G d) := by  haveI : Nonempty V := hconn.nonempty  have hne_ediam : G.ediam ≠ ⊤ := SimpleGraph.connected_iff_ediam_ne_top.mp hconn  have htop : ∀ d : ℕ, 3 ≤ d → simple_graph_power G d = ⊤ := by    intro d hd    ext u v    constructor    · intro h; exact h.1    · intro huv      refine ⟨huv, ?_⟩      have hreach : G.Reachable u v := hconn u v      have hne : G.edist u v ≠ ⊤ := SimpleGraph.edist_ne_top_iff_reachable.mpr hreach      have htoNat : (G.edist u v).toNat ≤ G.diam :=        ENat.toNat_le_toNat SimpleGraph.edist_le_ediam hne_ediam      have heq : G.edist u v = ((G.edist u v).toNat : ℕ∞) :=        (ENat.natCast_toNat_eq_self.mpr hne).symm      rw [heq]      have hle : (G.edist u v).toNat ≤ d := le_trans htoNat (le_trans hdiam hd)      exact_mod_cast hle  intro d hd  rcases d with _ | _ | _ | k  · omega  · rw [simple_graph_power_one]; exact hwc1  · exact hwc2  · have htopd : simple_graph_power G (k + 3) = ⊤ := htop (k + 3) (by omega)    rw [htopd]    exact forall_power_well_covered_of_well_covered_diam_le_three_aux_top
See it in the graphDiscuss this resultChallenge it