For an undirected graph G = (V, E) a subset of I of V is called independent when no two vertices in I are adjacent. If, in addition, I ˆª {x} is not independent for each x ˆˆ V - I, then we say that I is a maximal independent set (of vertices).
The two graphs in Fig. 12.50 are examples of special kinds of trees called caterpillars. In general, a tree T = (V, E) is a caterpillar when there is a (maximal) path p such that, for all v ˆˆ V, either v is on the path p or i; is adjacent to a vertex on the path p. This path p is called the spine of the caterpillar.

(a) How many maximal independent sets of vertices are there for each of the caterpillars in parts (i) and (ii) of Fig. 12.50?
(b) For n ˆˆ Z+, with n ‰¥ 3, let an count the number of maximal independent sets in a caterpillar T whose spine contains n vertices. Find and solve a recurrence relation for an. [The reader may wish to reexamine part (a) of Supplementary Exercise 21 in Chapter 11.]

V3 Spine vs v W3 Ws W1 W2 () pine w, W2, W3, Wa, W