A caterpillar graph, caterpillar tree, or simply "caterpillar," is a tree in which every graph vertex
is on a central stalk or only one graph edge away from
the stalk (in other words, removal of its endpoints
leaves a path graph; Gallian 2007). A tree
is a caterpillar iff all nodes
of degree 
are surrounded by at most two nodes
of degree two or greater.
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 caterpillar trees on 
nodes is
 |
where 
is the floor function (Harary and Schwenk 1973).
For 
,
2, ... nodes, this gives 1, 1, 1, 2, 3, 6, 10, 20,
36, 72, 136, ... (OEIS A005418). The first
few caterpillars are illustrated above.
The numbers of noncaterpillar trees on 
, 8, ... are 1, 3, 11, 34, 99, ... (OEIS A052471).
The noncaterpillar trees on 
nodes are illustrated
above.
