AFTD Auto-Formalizing Theoretical Domains

simple_graph_power_well_covered_not_ball_union_subset

theoremverifiedformalization

Let G be a finite graph and d ≥ 1 with G^d well-covered. Then there are no vertices s, t, w with d_G(s, t) ≥ d + 1 and B_d(s) ∪ B_d(t) ⊆ B_d(w), where B_d(x) is the set of vertices at distance at most d from x.

Statement

theorem simple_graph_power_well_covered_not_ball_union_subset {V : Type*} [Fintype V]
    [DecidableEq V] (G : SimpleGraph V) (d : ℕ) (hd : 1 ≤ d)
    (hwc : simple_graph_is_well_covered (simple_graph_power G d)) (s t w : V)
    (hst : ((d + 1 : ℕ) : ℕ∞) ≤ G.edist s t) :
    ¬ ∀ x : V, (G.edist s x ≤ d ∨ G.edist t x ≤ d) → G.edist w x ≤ d
Formalizes
arXiv:2610.09300 (On graphs whose powers are well-covered), Lemma 2.7. The proof uses well-coveredness directly (two maximal independent sets of different sizes) instead of the independence number.
Verified
11 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • 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…
  • simple_graph_exists_maximal_indep_supersetIn a finite graph every independent set is contained in a maximal independent set.
Used by 2

The proof, explained

We argue by contradiction: suppose there exist vertices s, t, w with d_G(s, t) ≥ d + 1 such that B_d(s) ∪ B_d(t) ⊆ B_d(w). In the power graph P = G^d, the vertices s and t are non-adjacent and both are distinct from w. We extend {w} to a maximal independent set X in P, which cannot contain s or t since both are adjacent to w in P. Replacing w with {s, t} gives a new independent set Y = (X \ {w}) ∪ {s, t}, because any neighbor of s or t in X \ {w} would belong to B_d(s) ∪ B_d(t) ⊆ B_d(w) and thus be adjacent to w, contradicting the independence of X. Extending Y to a maximal independent set Z gives |Z| ≥ |Y| = |X| + 1, contradicting the hypothesis that P is well-covered.

  1. Assume for contradiction that B_d(s) ∪ B_d(t) ⊆ B_d(w), and deduce that d_G(w, s) ≤ d and d_G(w, t) ≤ d.

    We assume for contradiction that every vertex within distance d of s or t is within distance d of w (hball). We set P = simple_graph_power G d. Since d_G(s, s) = 0 ≤ d, vertex s is in B_d(s) and hence in B_d(w), showing d_G(w, s) ≤ d (hsw). Similarly, d_G(t, t) = 0 ≤ d implies d_G(w, t) ≤ d (htw).

    lines 6–9

      intro hball
      set P := simple_graph_power G d
      have hsw : G.edist w s ≤ d := hball s (Or.inl (by simp))
      have htw : G.edist w t ≤ d := hball t (Or.inr (by simp))
  2. Show that distance at most d is incompatible with distance at least d + 1, and deduce that s, t, w are pairwise distinct.

    First, having both d_G(x, y) ≤ d and d + 1 ≤ d_G(x, y) gives d + 1 ≤ d by transitivity, an impossibility (hlt). If s = t, then d_G(s, t) = 0 ≥ d + 1 ≥ 2, a contradiction; hence s ≠ t (hst_ne). If w = s, then d_G(s, t) = d_G(w, t) ≤ d, contradicting d_G(s, t) ≥ d + 1; hence w ≠ s (hws). Finally, if w = t, symmetry of distance (SimpleGraph.edist_comm) yields d_G(s, t) = d_G(s, w) = d_G(w, s) ≤ d, again contradicting d_G(s, t) ≥ d + 1; hence w ≠ t (hwt).

    lines 10–20

    uses SimpleGraph.edist_comm

      have hlt : ∀ x y : V, G.edist x y ≤ d → ¬ ((d + 1 : ℕ) : ℕ∞) ≤ G.edist x y := by
        intro x y h1 h2
        have := h2.trans h1
        norm_cast at this
        omega
      have hst_ne : s ≠ t := by
        intro h; subst h; simp at hst
      have hws : w ≠ s := by
        intro h; subst h; exact hlt w t htw hst
      have hwt : w ≠ t := by
        intro h; subst h; rw [SimpleGraph.edist_comm] at hsw; exact hlt s w hsw hst
  3. Extend {w} to a maximal independent set X in P, and show that neither s nor t belongs to X.

    Any vertex x ≠ w in B_d(s) ∪ B_d(t) has d_G(w, x) ≤ d and thus is adjacent to w in P (hadjw). The singleton {w} is independent in P, so it extends to a maximal independent set X with w ∈ X (simple_graph_exists_maximal_indep_superset, Finset.mem_singleton_self). Since s ≠ w and d_G(s, s) ≤ d, vertex s is adjacent to w in P; because X is independent and w ∈ X, we have s ∉ X (hsX). By the same argument for t, t ∉ X (htX).

    lines 21–26

    uses simple_graph_exists_maximal_indep_superset, Finset.mem_singleton_self

      have hadjw : ∀ x, x ≠ w → (G.edist s x ≤ d ∨ G.edist t x ≤ d) → P.Adj w x :=
        fun x hx h => ⟨fun e => hx e.symm, hball x h⟩
      obtain ⟨X, hwX, hX⟩ := simple_graph_exists_maximal_indep_superset P {w} (by simp)
      have hwX' : w ∈ X := hwX (Finset.mem_singleton_self w)
      have hsX : s ∉ X := fun h => hX.1 hwX' h hws (hadjw s hws.symm (Or.inl (by simp)))
      have htX : t ∉ X := fun h => hX.1 hwX' h hwt (hadjw t hwt.symm (Or.inr (by simp)))
  4. The set Y = (X \ {w}) ∪ {s, t} is independent in P.

    We check that no two distinct vertices in Y are adjacent in P. If some x ∈ X \ {w} were adjacent to y ∈ {s, t}, then d_G(y, x) ≤ d, placing x in B_d(s) ∪ B_d(t). Since x ≠ w, this would make x adjacent to w in P, which is impossible because both w, x ∈ X and X is independent (the helper lemma key). Vertices within X \ {w} are non-adjacent because X is independent (Finset.mem_of_mem_erase). Finally, s and t cannot be adjacent in P because d_G(s, t) ≥ d + 1 > d. Thus Y is an independent set in P.

    lines 27–51

    uses Finset.mem_erase, Finset.mem_insert, Finset.mem_singleton, Finset.coe_union, Set.mem_union, Finset.mem_coe, Finset.mem_of_mem_erase

      set Y := X.erase w ∪ {s, t}
      have hYind : P.IsIndepSet (Y : Set V) := by
        have key : ∀ x ∈ X.erase w, ∀ y ∈ ({s, t} : Finset V), ¬ P.Adj y x := by
          intro x hx y hy hadj
          rw [Finset.mem_erase] at hx
          have hyx : G.edist y x ≤ d := hadj.2
          simp only [Finset.mem_insert, Finset.mem_singleton] at hy
          have : P.Adj w x := by
            rcases hy with rfl | rfl
            · exact hadjw x hx.1 (Or.inl hyx)
            · exact hadjw x hx.1 (Or.inr hyx)
          exact hX.1 hwX' hx.2 (fun e => hx.1 e.symm) this
        intro x hx y hy hxy hadj
        simp only [Y, Finset.coe_union, Set.mem_union, Finset.mem_coe] at hx hy
        rcases hx with hx | hx <;> rcases hy with hy | hy
        · exact hX.1 (Finset.mem_of_mem_erase hx) (Finset.mem_of_mem_erase hy) hxy hadj
        · exact key x hx y hy hadj.symm
        · exact key y hy x hx hadj
        · simp only [Finset.mem_insert, Finset.mem_singleton] at hx hy
          have hst' : ¬ P.Adj s t := fun h => hlt s t h.2 hst
          rcases hx with rfl | rfl <;> rcases hy with rfl | rfl
          · exact hxy rfl
          · exact hst' hadj
          · exact hst' hadj.symm
          · exact hxy rfl
  5. Extend Y to a maximal independent set Z in P, and show |Y| = |X| + 1.

    The independent set Y extends to a maximal independent set Z in P (simple_graph_exists_maximal_indep_superset). Since neither s nor t is in X, the sets X \ {w} and {s, t} are disjoint (Finset.disjoint_left). The cardinality of their union is therefore |X \ {w}| + |{s, t}| (Finset.card_union_of_disjoint). Since w ∈ X, erasing w gives |X| - 1 (Finset.card_erase_of_mem), and because s ≠ t, |{s, t}| = 2 (Finset.card_pair). Thus |Y| = (|X| - 1) + 2 = |X| + 1.

    lines 52–64

    uses simple_graph_exists_maximal_indep_superset, Finset.disjoint_left, Finset.mem_insert, Finset.mem_singleton, Finset.mem_of_mem_erase, Finset.card_union_of_disjoint, Finset.card_erase_of_mem, Finset.card_pair

      obtain ⟨Z, hYZ, hZ⟩ := simple_graph_exists_maximal_indep_superset P Y hYind
      have hcardY : Y.card = X.card + 1 := by
        have hdisj : Disjoint (X.erase w) {s, t} := by
          rw [Finset.disjoint_left]
          intro x hx hx'
          simp only [Finset.mem_insert, Finset.mem_singleton] at hx'
          rcases hx' with rfl | rfl
          · exact hsX (Finset.mem_of_mem_erase hx)
          · exact htX (Finset.mem_of_mem_erase hx)
        rw [Finset.card_union_of_disjoint hdisj, Finset.card_erase_of_mem hwX',
          Finset.card_pair hst_ne]
        have : 1 ≤ X.card := Finset.card_pos.2 ⟨w, hwX'⟩
        omega
  6. Derive a contradiction: |Z| ≥ |X| + 1 contradicts well-coveredness, which requires |Z| = |X|.

    Since Y ⊆ Z, we have |Y| ≤ |Z| (Finset.card_le_card), so |Z| ≥ |X| + 1. But P is well-covered (hwc), so all maximal independent sets have the same size, which forces |X| = |Z|. This gives |X| ≥ |X| + 1, an arithmetic impossibility that omega resolves to conclude False.

    lines 65–67

    uses Finset.card_le_card

      have h1 := Finset.card_le_card hYZ
      have h2 := hwc X Z hX hZ
      omega
SimpleGraph.edist_comm
Extended distance between vertices in a graph is symmetric: d_G(u, v) = d_G(v, u).
simple_graph_exists_maximal_indep_superset
Every independent set in a finite graph extends to an inclusion-maximal independent set.
Finset.mem_singleton_self
An element is a member of its own singleton set: a ∈ {a}.
Finset.mem_erase
An element is in s.erase b if and only if it is in s and distinct from b.
Finset.mem_insert
An element belongs to insert b s if and only if it equals b or is in s.
Finset.mem_singleton
An element belongs to {a} if and only if it equals a.
Finset.coe_union
The coercion of a union of finite sets to a Set equals the union of their coercions: ↑(s₁ ∪ s₂) = ↑s₁ ∪ ↑s₂.
Set.mem_union
An element belongs to a ∪ b if and only if it belongs to a or to b.
Finset.mem_coe
Membership in the coerced Set ↑s is equivalent to membership in the Finset s.
Finset.mem_of_mem_erase
If an element belongs to s.erase a, then it belongs to s.
Finset.disjoint_left
Two finite sets are disjoint if and only if no element of the first belongs to the second.
Finset.card_union_of_disjoint
If two finite sets are disjoint, the cardinality of their union is the sum of their cardinalities.
Finset.card_erase_of_mem
Removing an element a from a finite set s of which it is a member decreases its cardinality by 1.
Finset.card_pair
If two elements are distinct, the pair {a, b} has cardinality 2.
Finset.card_le_card
If s ⊆ t for finite sets, then |s| ≤ |t|.

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 simple_graph_power_well_covered_not_ball_union_subset {V : Type*} [Fintype V]    [DecidableEq V] (G : SimpleGraph V) (d : ℕ) (hd : 1 ≤ d)    (hwc : simple_graph_is_well_covered (simple_graph_power G d)) (s t w : V)    (hst : ((d + 1 : ℕ) : ℕ∞) ≤ G.edist s t) :    ¬ ∀ x : V, (G.edist s x ≤ d ∨ G.edist t x ≤ d) → G.edist w x ≤ d := by  intro hball  set P := simple_graph_power G d  have hsw : G.edist w s ≤ d := hball s (Or.inl (by simp))  have htw : G.edist w t ≤ d := hball t (Or.inr (by simp))  have hlt : ∀ x y : V, G.edist x y ≤ d → ¬ ((d + 1 : ℕ) : ℕ∞) ≤ G.edist x y := by    intro x y h1 h2    have := h2.trans h1    norm_cast at this    omega  have hst_ne : s ≠ t := by    intro h; subst h; simp at hst  have hws : w ≠ s := by    intro h; subst h; exact hlt w t htw hst  have hwt : w ≠ t := by    intro h; subst h; rw [SimpleGraph.edist_comm] at hsw; exact hlt s w hsw hst  have hadjw : ∀ x, x ≠ w → (G.edist s x ≤ d ∨ G.edist t x ≤ d) → P.Adj w x :=    fun x hx h => ⟨fun e => hx e.symm, hball x h⟩  obtain ⟨X, hwX, hX⟩ := simple_graph_exists_maximal_indep_superset P {w} (by simp)  have hwX' : w ∈ X := hwX (Finset.mem_singleton_self w)  have hsX : s ∉ X := fun h => hX.1 hwX' h hws (hadjw s hws.symm (Or.inl (by simp)))  have htX : t ∉ X := fun h => hX.1 hwX' h hwt (hadjw t hwt.symm (Or.inr (by simp)))  set Y := X.erase w ∪ {s, t}  have hYind : P.IsIndepSet (Y : Set V) := by    have key : ∀ x ∈ X.erase w, ∀ y ∈ ({s, t} : Finset V), ¬ P.Adj y x := by      intro x hx y hy hadj      rw [Finset.mem_erase] at hx      have hyx : G.edist y x ≤ d := hadj.2      simp only [Finset.mem_insert, Finset.mem_singleton] at hy      have : P.Adj w x := by        rcases hy with rfl | rfl        · exact hadjw x hx.1 (Or.inl hyx)        · exact hadjw x hx.1 (Or.inr hyx)      exact hX.1 hwX' hx.2 (fun e => hx.1 e.symm) this    intro x hx y hy hxy hadj    simp only [Y, Finset.coe_union, Set.mem_union, Finset.mem_coe] at hx hy    rcases hx with hx | hx <;> rcases hy with hy | hy    · exact hX.1 (Finset.mem_of_mem_erase hx) (Finset.mem_of_mem_erase hy) hxy hadj    · exact key x hx y hy hadj.symm    · exact key y hy x hx hadj    · simp only [Finset.mem_insert, Finset.mem_singleton] at hx hy      have hst' : ¬ P.Adj s t := fun h => hlt s t h.2 hst      rcases hx with rfl | rfl <;> rcases hy with rfl | rfl      · exact hxy rfl      · exact hst' hadj      · exact hst' hadj.symm      · exact hxy rfl  obtain ⟨Z, hYZ, hZ⟩ := simple_graph_exists_maximal_indep_superset P Y hYind  have hcardY : Y.card = X.card + 1 := by    have hdisj : Disjoint (X.erase w) {s, t} := by      rw [Finset.disjoint_left]      intro x hx hx'      simp only [Finset.mem_insert, Finset.mem_singleton] at hx'      rcases hx' with rfl | rfl      · exact hsX (Finset.mem_of_mem_erase hx)      · exact htX (Finset.mem_of_mem_erase hx)    rw [Finset.card_union_of_disjoint hdisj, Finset.card_erase_of_mem hwX',      Finset.card_pair hst_ne]    have : 1 ≤ X.card := Finset.card_pos.2 ⟨w, hwX'⟩    omega  have h1 := Finset.card_le_card hYZ  have h2 := hwc X Z hX hZ  omega
See it in the graphDiscuss this resultChallenge it