Caterpillar tree Created 2026-10-20 Updated 2026-11-05
A caterpillar tree is a tree whose non-leaf vertices lie on a single path, called its spine. Equivalently, deleting all degree-one vertices leaves a path, a single vertex, or an empty graph in the smallest cases. A star graph is a caterpillar tree with a one-vertex spine; every path graph is also a caterpillar tree. Trees with branching that persists after deleting the leaves fail the definition. The spine packages a seemingly branching structure into a linear backbone with attached leaves, which simplifies many counting and layout questions.
Lobster tree 2026-10-20
Spine of a caterpillar tree 2026-11-05
The spine of a caterpillar tree, in the pruned-spine convention, is the induced subgraph on its non-leaf vertices. It is obtained by deleting every degree-one vertex once, simultaneously. For a caterpillar it is a path or a single vertex; in the two-vertex case it is empty. A one-vertex tree can be handled as a single-vertex spine.
For a path on five vertices , the pruned spine is . For a star with at least three vertices it is the hub alone. Every other vertex is a leaf attached to this linear backbone, explaining the caterpillar shape.
Some descriptions call an extended path containing all non-leaf vertices a spine as well; such an extension can include endpoint leaves and need not be unique. The pruned convention fixes the canonical core. Repeatedly deleting leaves until only a center remains is a different operation: doing that to an arbitrary tree does not test whether its one-step pruned core was a path.