AFTD Auto-Formalizing Theoretical Domains

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

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.

  1. 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.

    line 2

    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
See it in the graphDiscuss this resultChallenge it