A caterpillar graph, caterpillar tree, or simply "caterpillar," is a tree containing a path graph such that every graph vertex is either on the path or joined to a graph vertex on the path by one graph edge. The singleton graph and the two-vertex tree are included. Equivalently, deleting all endpoints leaves the empty graph on 0 vertices or a path graph, possibly consisting of a single graph vertex. Harary and Schwenk (1973, p. 361) give the leaf-deletion definition for trees with at least three vertices. A tree is a caterpillar iff each graph vertex of degree at least 3 has at most two neighbors of degree at least 2.
An n-alkane graph is also sometimes known as a caterpillar graph (Boesch et al. 1974; Merrifield and Simmons 1989, pp. 161-162).
Caterpillar graphs are graceful.
The number of nonisomorphic caterpillar trees on 
nodes is
 |
where 
is the floor function (Harary and Schwenk 1973).
With 
,
the counts for 
,
2, ... nodes are 1, 1, 1, 2, 3, 6, 10, 20, 36, 72,
136, ..., where 
for 
(OEIS A005418). The first few caterpillars
are illustrated above.
The numbers of nonisomorphic noncaterpillar trees on 
, 8, ... are 1, 3, 11, 34, 99, ... (OEIS A052471).
The noncaterpillar trees on 
nodes are illustrated
above.
