Alternate Fibonacci Numbers
In this chapter, we shall provide a variety of examples that are counted by alternate Fibonacci numbers—that is, subsequences of the Fibonacci numbers, such as 1(= F1), 2(= F3), 5(= F5), 13(= F7), . . ., or 1(= F2), 3(= F4), 8(= F6), 21(= F8), . . . .
Example 16.1: Our first example deals with the undirected graph Gn shown in Fig. 16.1. This graph has the n + 1 vertices: , and the n + (n − 1) = 2n − 1 edges:
It is called the fan on n vertices.
For n = 2, the undirected graph G2 is shown in Fig. 16.2(a). In Fig. 16.2(b) there are three subgraphs of G2. Note that each of these subgraphs contains all three vertices of G2, contains no loops or cycles, and is connected. These are the three spanning trees of G2.
The fan for n = 3 is shown in Fig. 16.3(a) on p. 128. In Fig. 16.3(b) we have three of the eight spanning trees for G3. Note how these three spanning trees can be obtained from the three spanning trees in Fig. 16.2 (b) by adding ...