(a) The graph in part (a) of Fig. 12.48 has exactly one spanning tree - namely, the graph itself. The graph in Fig. 12.48(b) has four nonidentical, though isomorphic, spanning trees. In part (c) of the figure we find three of the nonidentical spanning trees for the graph in part (d). Note that T2 and T3 are isomorphic, but T1 is not isomorphic to T2 (or T3). How many nonidentical spanning trees exist for the graph in Fig. 12.48(d)?
(b) In Fig. 12.48(e) we generalize the graphs in parts (a), (b), and (d) of the figure. For each n ˆˆ Z+, the graph Gn is K2,n.
If tn counts the number of nonidentical spanning trees for Gn, find and solve a recurrence relation for tn.

Transcribed Image Text:

(c) T T.