AFTD Auto-Formalizing Theoretical Domains

is_piece_thread

def

A 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 endpoints are either special or have degree at least 3.

Statement

def is_piece_thread {V : Type*} [Fintype V] [DecidableEq V]
    (T : SimpleGraph V) [DecidableRel T.Adj] {u v : V} (p : T.Walk u v) : Prop
Defined in
arXiv:2610.15145, Section 10 and Question 11.4
Verified
25 Oct 2026
Axioms
none listed
Built on 1
  • is_tree_specialA 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).
Used by 3
  • 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

Definition of a predicate is_piece_thread on a walk p between vertices u and v in a simple graph T over a finite type V with decidable equality and decidable adjacency. The predicate asserts that all of the following hold: 1. p is a path (p.IsPath, i.e., it contains no repeated vertices). 2. The length of p is at least 1 (1 ≤ p.length). 3. For the starting vertex u, either u is tree-special in T (is_tree_special T u), or u has degree at least 3 and is not tree-special in T (which is logically equivalent to: is_tree_special T u ∨ 3 ≤ T.degree u). 4. For the ending vertex v, either v is tree-special in T (is_tree_special T v), or v has degree at least 3 and is not tree-special in T (which is logically equivalent to: is_tree_special T v ∨ 3 ≤ T.degree v). 5. For every internal vertex x of p (that is, every vertex in (p.support.drop 1).dropLast), x has degree 2 in T (T.degree x = 2) and x is not tree-special in T (¬ is_tree_special T x).

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 thread of a piece in a tree is a maximal path whose interior vertices have degree 2 and are not special. -/
def is_piece_thread {V : Type*} [Fintype V] [DecidableEq V]
    (T : SimpleGraph V) [DecidableRel T.Adj] {u v : V} (p : T.Walk u v) : Prop := p.IsPath ∧ 1 ≤ p.length ∧
  (is_tree_special T u ∨ (3 ≤ T.degree u ∧ ¬ is_tree_special T u)) ∧
  (is_tree_special T v ∨ (3 ≤ T.degree v ∧ ¬ is_tree_special T v)) ∧
  ∀ x ∈ (p.support.drop 1).dropLast, T.degree x = 2 ∧ ¬ is_tree_special T x
See it in the graphDiscuss this resultChallenge it