AFTD Auto-Formalizing Theoretical Domains

is_tree_special

def

A vertex in a graph is special if it is not a leaf (degree not equal to 1) but is adjacent to a leaf (degree 1).

Statement

def is_tree_special {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (v : V) : Prop
Defined in
arXiv:2610.15145, Definition 2.1
Verified
25 Oct 2026
Axioms
none listed
Used by 4
  • is_piece_threadA thread of a piece of a tree T is a path of length at least 1 whose interior vertices have degree 2 and are not special, and whose…
  • is_internal_piece_threadAn internal thread of a piece of a tree T is a piece thread whose endpoints both have degree at least 3 in T and are not special.
  • is_leaf_piece_threadA leaf thread of a piece of a tree T is a piece thread at least one of whose endpoints is a special vertex of T.
  • arrows_grundy_three_witness_tree_structureThe explicit 21-vertex graph defined by 20 edges is a tree of maximum degree at most 3, all of whose piece threads have length at most 3.

Read back from the Lean

For a finite type V with decidable equality, a simple graph G on V with decidable adjacency, and a vertex v : V, is_tree_special G v is defined to hold if and only if the degree of v in G is not equal to 1, and there exists a vertex u : V adjacent to v in G whose degree in G is equal to 1.

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 vertex in a graph is special if it is not a leaf but is adjacent to a leaf. -/
def is_tree_special {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (v : V) : Prop := G.degree v ≠ 1 ∧ ∃ u, G.Adj u v ∧ G.degree u = 1
See it in the graphDiscuss this resultChallenge it