AFTD Auto-Formalizing Theoretical Domains

simple_graph_has_well_covered_powers

def

A finite simple graph G has the well-covered powers property if for every integer d ≥ 1, the d-th graph power G^d is well-covered.

Statement

def simple_graph_has_well_covered_powers {V : Type*} [Fintype V] (G : SimpleGraph V) : Prop
Defined in
arXiv:2611.03956 Def 2.2
Verified
04 Nov 2026
Axioms
none listed
Built on 2
  • 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…
Used by 2

Read back from the Lean

Given a finite type $V$ and a simple graph $G$ on $V$, the predicate simple_graph_has_well_covered_powers G asserts that for every natural number $d \ge 1$, the $d$-th graph power of $G$ is well-covered (that is, all maximal independent sets of vertices 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.

Lean source view module on GitHub

/-- A finite simple graph has the well-covered powers property if every positive power G^d is well-covered. -/
def simple_graph_has_well_covered_powers {V : Type*} [Fintype V] (G : SimpleGraph V) : Prop := ∀ d : ℕ, 1 ≤ d → simple_graph_is_well_covered (simple_graph_power G d)
See it in the graphDiscuss this resultChallenge it