AFTD Auto-Formalizing Theoretical Domains

forall_power_well_covered_of_well_covered_diam_le_two

theoremverifiedformalization

Let G be a finite connected well-covered graph of diameter at most 2. Then G^d is well-covered for every d ≥ 1.

Statement

theorem forall_power_well_covered_of_well_covered_diam_le_two {V : Type*} [Fintype V]
    (G : SimpleGraph V) (hconn : G.Connected) (hdiam : G.diam ≤ 2)
    (hwc : simple_graph_is_well_covered G) :
    ∀ d : ℕ, 1 ≤ d → simple_graph_is_well_covered (simple_graph_power G d)
Formalizes
arXiv:2610.09300 (On graphs whose powers are well-covered), Sec. 3, remark before Question 3.9 ('every well-covered graph of diameter 2 automatically satisfies this condition'); stated for diameter at most 2.
Verified
11 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • simple_graph_power_oneG^1 = G.
  • 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…
Used by 4

The proof, explained

To show that G^d is well-covered for all d ≥ 1, the proof splits into two cases: d = 1 and d ≥ 2. When d = 1, the power graph G^1 is G itself, which is well-covered by hypothesis. When d ≥ 2, the assumption diam(G) ≤ 2 implies that every pair of distinct vertices has distance at most d and is therefore adjacent in G^d. Consequently, G^d is a complete graph, so every maximal independent set has size exactly 1, proving that G^d is well-covered.

  1. For d = 1, the power graph G^1 is well-covered.

    We introduce the exponent d ≥ 1 and divide into cases d < 2 and d ≥ 2. In the case d < 2, linear arithmetic implies d = 1. The first power G^1 is identically G, so well-coveredness follows immediately from the assumption that G is well-covered.

    lines 5–10

    uses Nat.lt_or_ge, simple_graph_power_one

      intro d hd
      rcases Nat.lt_or_ge d 2 with h1 | h2
      · have : d = 1 := by omega
        subst this
        rw [simple_graph_power_one]
        exact hwc
  2. When d ≥ 2, the distance in G between any two vertices is at most d.

    For d ≥ 2, graph connectedness implies the vertex set V is nonempty and the extended diameter ediam(G) is finite. The distance between any two vertices u, v ∈ V is at most ediam(G), which equals diam(G) because the extended diameter is finite. Since diam(G) ≤ 2 ≤ d, the distance between u and v is at most d.

    lines 11–17

    uses SimpleGraph.connected_iff_ediam_ne_top, SimpleGraph.edist_le_ediam, SimpleGraph.diam, ENat.natCast_toNat

      · have : Nonempty V := hconn.nonempty
        have htop : G.ediam ≠ ⊤ := (SimpleGraph.connected_iff_ediam_ne_top).1 hconn
        have hed : ∀ u v : V, G.edist u v ≤ d := by
          intro u v
          calc G.edist u v ≤ G.ediam := SimpleGraph.edist_le_ediam
            _ = G.diam := by rw [SimpleGraph.diam]; exact (ENat.natCast_toNat htop).symm
            _ ≤ d := by exact_mod_cast hdiam.trans h2
  3. When d ≥ 2, every maximal independent set in G^d has cardinality 1.

    Let s be a maximal independent set in G^d. To show |s| = 1, we show s = {a} for some vertex a. If s were empty, any singleton {v} from the nonempty vertex set would be an independent set, contradicting the maximality of ∅. Thus s is nonempty, containing some vertex a. If s contained another vertex b ≠ a, then since dist(b, a) ≤ d, vertices b and a would be adjacent in G^d, contradicting that s is independent. Hence a is the unique element of s, so s = {a} and |s| = 1.

    lines 18–33

    uses Finset.card_eq_one, Finset.eq_singleton_iff_unique_mem, Finset.not_nonempty_iff_eq_empty, Finset.empty_subset

        have hcard : ∀ s : Finset V,
            Maximal (fun u : Finset V => (simple_graph_power G d).IsIndepSet (u : Set V)) s →
              s.card = 1 := by
          intro s hs
          rw [Finset.card_eq_one]
          obtain ⟨v⟩ := ‹Nonempty V›
          by_cases hne : s.Nonempty
          · obtain ⟨a, ha⟩ := hne
            refine ⟨a, Finset.eq_singleton_iff_unique_mem.2 ⟨ha, fun b hb => ?_⟩⟩
            by_contra hba
            exact hs.1 hb ha hba ⟨hba, hed b a⟩
          · rw [Finset.not_nonempty_iff_eq_empty] at hne
            subst hne
            have hv : (simple_graph_power G d).IsIndepSet (({v} : Finset V) : Set V) := by simp
            have := hs.2 hv (Finset.empty_subset _)
            simp at this
  4. When d ≥ 2, G^d is well-covered.

    Given two maximal independent sets s and t of G^d, each has cardinality 1 by the previous step. Thus |s| = |t| = 1, which proves that G^d is well-covered.

    lines 34–35

        intro s t hs ht
        rw [hcard s hs, hcard t ht]
Nat.lt_or_ge
For any natural numbers n and m, either n < m or n ≥ m.
simple_graph_power_one
The first power of a simple graph G is equal to G itself.
SimpleGraph.connected_iff_ediam_ne_top
A nonempty finite graph is connected if and only if its extended diameter is not infinite (⊤).
SimpleGraph.edist_le_ediam
The extended distance between any two vertices in a graph is bounded by its extended diameter.
SimpleGraph.diam
The definition of graph diameter as the natural number value of the extended diameter.
ENat.natCast_toNat
Casting a finite extended natural number to a natural number and back yields the original value.
Finset.card_eq_one
A finite set has cardinality 1 if and only if it is a singleton {a}.
Finset.eq_singleton_iff_unique_mem
A finite set s equals {a} if and only if a ∈ s and every element of s equals a.
Finset.not_nonempty_iff_eq_empty
A finite set is not nonempty if and only if it is empty.
Finset.empty_subset
The empty set is a subset of any finite set.

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

theorem forall_power_well_covered_of_well_covered_diam_le_two {V : Type*} [Fintype V]    (G : SimpleGraph V) (hconn : G.Connected) (hdiam : G.diam ≤ 2)    (hwc : simple_graph_is_well_covered G) :    ∀ d : ℕ, 1 ≤ d → simple_graph_is_well_covered (simple_graph_power G d) := by  intro d hd  rcases Nat.lt_or_ge d 2 with h1 | h2  · have : d = 1 := by omega    subst this    rw [simple_graph_power_one]    exact hwc  · have : Nonempty V := hconn.nonempty    have htop : G.ediam ≠ ⊤ := (SimpleGraph.connected_iff_ediam_ne_top).1 hconn    have hed : ∀ u v : V, G.edist u v ≤ d := by      intro u v      calc G.edist u v ≤ G.ediam := SimpleGraph.edist_le_ediam        _ = G.diam := by rw [SimpleGraph.diam]; exact (ENat.natCast_toNat htop).symm        _ ≤ d := by exact_mod_cast hdiam.trans h2    have hcard : ∀ s : Finset V,        Maximal (fun u : Finset V => (simple_graph_power G d).IsIndepSet (u : Set V)) s →          s.card = 1 := by      intro s hs      rw [Finset.card_eq_one]      obtain ⟨v⟩ := ‹Nonempty V›      by_cases hne : s.Nonempty      · obtain ⟨a, ha⟩ := hne        refine ⟨a, Finset.eq_singleton_iff_unique_mem.2 ⟨ha, fun b hb => ?_⟩⟩        by_contra hba        exact hs.1 hb ha hba ⟨hba, hed b a⟩      · rw [Finset.not_nonempty_iff_eq_empty] at hne        subst hne        have hv : (simple_graph_power G d).IsIndepSet (({v} : Finset V) : Set V) := by simp        have := hs.2 hv (Finset.empty_subset _)        simp at this    intro s t hs ht    rw [hcard s hs, hcard t ht]
See it in the graphDiscuss this resultChallenge it