Chapter 16

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(= F_{1}), 2(= F_{3}), 5(= F_{5}), 13(= F_{7}), . . ., or 1(= F_{2}), 3(= F_{4}), 8(= F_{6}), 21(= F_{8}), . . . .

Example 16.1: Our first example deals with the undirected graph G_{n} 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 G_{2} is shown in Fig. 16.2(a). In Fig. 16.2(b) there are three subgraphs of G_{2}. Note that each of these subgraphs contains all three vertices of G_{2}, contains no loops or cycles, and is connected. These are the three spanning trees of G_{2}.

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 G_{3}. Note how these three spanning trees can be obtained from the three spanning trees in Fig. 16.2 (b) by adding ...