AFTD Auto-Formalizing Theoretical Domains

graph_dismantling_class

inductive

The dismantling class $\mathcal{D}_j$ for integer $j \ge -1$: $\mathcal{D}_{-1}$ is the class of non-empty cones, and for $j \ge 0$, a non-empty graph belongs to $\mathcal{D}_j$ if it can be reduced to $K_1$ by successive deletions of vertices whose open neighbourhood graph belongs to $\mathcal{D}_{j-1}$.

Statement

inductive graph_dismantling_class : ℤ → (V : Type) → SimpleGraph V → Prop
Defined in
arXiv:2611.14430 Definition 2.2
Verified
11 Nov 2026
Axioms
none listed
Used by 1
  • graph_is_strictly_dismantlableA simple graph G on a vertex type V is strictly k-dismantlable (for an integer k) if G belongs to dismantling class k and does not belong…

Read back from the Lean

An inductive predicate graph_dismantling_class : ℤ → (V : Type) → SimpleGraph V → Prop asserting that a simple graph G on vertex type V belongs to the dismantling class at level j : ℤ, defined by the following constructors: 1. cone: For any type V and simple graph G on V, if V is nonempty and there exists a vertex apex : V adjacent to all other vertices (∀ v : V, v ≠ apex → G.Adj apex v), then graph_dismantling_class (-1) V G holds. 2. single: For any integer j ≥ 0, type V, and simple graph G on V, if V is nonempty and a subsingleton (i.e., V has exactly one element), then graph_dismantling_class j V G holds. 3. step: For any integer j ≥ 0, type V, simple graph G on V, and vertex v : V, if: - the induced subgraph of G on the open neighborhood of v (G.neighborSet v) belongs to graph_dismantling_class (j - 1), and - the induced subgraph of G on V \ {v} ({w : V | w ≠ v}) belongs to graph_dismantling_class j, then graph_dismantling_class j V G holds.

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

/-- The dismantling class D_j: D_{-1} is non-empty cones, and for j >= 0, D_j graphs reduce to K_1 by deleting vertices whose open neighbourhoods belong to D_{j-1}. -/
inductive graph_dismantling_class : ℤ → (V : Type) → SimpleGraph V → Prop where
  | cone (V : Type) (G : SimpleGraph V) (h : Nonempty V ∧ ∃ apex : V, ∀ v : V, v ≠ apex → G.Adj apex v) :
      graph_dismantling_class (-1) V G
  | single (j : ℤ) (hj : 0 ≤ j) (V : Type) (G : SimpleGraph V) (h : Nonempty V ∧ Subsingleton V) :
      graph_dismantling_class j V G
  | step (j : ℤ) (hj : 0 ≤ j) (V : Type) (G : SimpleGraph V) (v : V)
      (h_elig : graph_dismantling_class (j - 1) ↑(G.neighborSet v) (G.induce (G.neighborSet v)))
      (h_rem : graph_dismantling_class j ↑{w : V | w ≠ v} (G.induce {w : V | w ≠ v})) :
      graph_dismantling_class j V G
See it in the graphDiscuss this resultChallenge it