is_caterpillar_isTree
theoremverified
Every caterpillar graph is a tree.
Statement
theorem is_caterpillar_isTree {V : Type*} (G : SimpleGraph V) (h : is_caterpillar G) : G.IsTree
- Source
- step towards caterpillar_third_t_chromatic_specialization_fiber_le_two
- Verified
- 27 Oct 2026
- Axioms
- none — Lean reports it depends on no axioms
- Built on 1
- is_caterpillarA 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.
- Used by 2
- 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.
The proof, explained
By definition, a caterpillar graph is a tree with an additional property: it contains a path such that every vertex is within distance at most one of the path. The theorem follows immediately by projecting the first conjunct from the definition of a caterpillar graph.
G is a tree (G.IsTree)
By definition, a graph G is a caterpillar if it is a tree and there exists a path within distance at most 1 from every vertex. The hypothesis h is this conjunction, so its first component (h.1) immediately gives that G is a tree.
theorem is_caterpillar_isTree {V : Type*} (G : SimpleGraph V) (h : is_caterpillar G) : G.IsTree := h.1
Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
/-- Every caterpillar graph is a tree. -/theorem is_caterpillar_isTree {V : Type*} (G : SimpleGraph V) (h : is_caterpillar G) : G.IsTree := h.1