AFTD Auto-Formalizing Theoretical Domains

is_caterpillar

def

A graph is a caterpillar if it is a tree containing a path such that every vertex is either on the path or adjacent to a vertex on the path.

Statement

def is_caterpillar {V : Type*} (G : SimpleGraph V) : Prop
Defined in
arXiv:2610.31785 Section 2.2; Harary-Schwenk 1973
Verified
27 Oct 2026
Axioms
none listed
Used by 3

Read back from the Lean

For a simple graph G on a type V, is_caterpillar G asserts that G is a tree (G.IsTree) and there exist vertices u, v : V and a walk p from u to v in G such that: 1. p is a path (p.IsPath, i.e., has no repeated vertices), and 2. for every vertex w : V, either w is in the vertex sequence (p.support) of p, or there exists a vertex z in p.support such that w is adjacent to z in G.

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 caterpillar is a tree that contains a path such that every vertex is on the path or adjacent to a vertex on the path. -/
def is_caterpillar {V : Type*} (G : SimpleGraph V) : Prop := G.IsTree ∧ ∃ (u v : V) (p : G.Walk u v), p.IsPath ∧ ∀ w : V, w ∈ p.support ∨ ∃ z ∈ p.support, G.Adj w z
See it in the graphDiscuss this resultChallenge it