Let G = (V, E) be the undirected connected "ladder graph" shown in Fig. 12.49. For n ‰¥ 0, let an count the number of spanning trees of G, whereas bn counts the number of these spanning trees that contain the edge {x1, y1}.
(a) Explain why an = an-1 + bn.
(b) Find an equation that expresses bn in terms of an-1 and bn-1.
(c) Use the results in parts (a) and (b) to set up and solve a recurrence relation for an.

Transcribed Image Text:

X1 X2 X3