(a) For n ≥ 1, let Pn-1 denote the path made up of n vertices and n - 1 edges. Let an be the number of independent subsets of vertices in Pn-1. (The empty subset is considered one of these independent subsets.) Find and solve a recurrence relation for an.
(b) Determine the number of independent subsets (of vertices) in each of the graphs G1, G2, and G3, of Fig. 11.100.
(c) For each of the graphs H1, H2, and H3, of Fig. 11.101, find the number of independent subsets of vertices.
(d) Let G = (V,E) be a loop-free undirected graph with V = {v1, v2, . ., vr] and where there are m independent subsets of vertices. The graph G' = (V', E') is constructed from G as follows: V' = V ∪ {x1, x2, . . ., with no xi in V, for all 1 ≤ / ≤ s; and E' = E ∪ {{x1,x2,;, vj}|l ≤ i ≤ j1 < j < r}. How many subsets of V' are independent?