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
- is_caterpillar_iso_of_card_le_threeAny two caterpillars on at most 3 vertices with equal vertex counts are isomorphic.
- caterpillar_card_eq_of_third_principal_specialization_eqIf two finite caterpillars have equal third principal specializations, their vertex sets have equal cardinalities.
- is_caterpillar_isTreeEvery caterpillar graph is a tree.
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