graph_dismantling_class
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