is_piece_thread
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