(a) Consider the subgraph of G (in Fig. 12.54) induced by the vertices a, b, c, d. This graph is called a kite. How many nonidentical (though some may be isomorphic) spanning trees are there for this kite?
(b) How many nonidentical (though some may be isomorphic) spanning trees of G do not contain the edge {c, h}?
(c) How many nonidentical (though some may be isomorphic) spanning trees of G contain all four of the edges {c, h}, {g, k], {l, p], and {d, o}?
(d) How many nonidentical (though some may be isomorphic) spanning trees exist for G?
(e) We generalize the graph G as follows. For n ‰¥ 2, start with a cycle on the In vertices v1, v2, ... , v2n-1, v2n. Replace each of the n edges {v1, v2], {v3, v4},... , {v2n-1, v2n} with a (labeled) kite so that the resulting graph is 3-regular. (The case for n = 4 appears in Fig. 12.54.) How many nonidentical (though some may be isomorphic) spanning trees are there for this graph?

Transcribed Image Text:

d. (G)