This quiz is about counting trees in certain classes of graphs.
Some (maybe all) of these results can be found in the web.
Nevertheless it is fun to discover them.

We consider the following classes of graphs:

- W(N): the wheel with N spokes, composed of a circle with N vertices and N edges, and a central vertex joined to the N vertices on the circle by N edges
- F(N): the fan with N edges, composed of a path of N edges and N+1 vertices, a central vertex, w, and the N+1 edges joining the vertices on the path to w.
- L(N): the ladder of length N, composed 2*(N+1) vertices, u
_{0}, ..., u_{N}, v_{0}, ..., v_{N}, and edges e_{k}=u_{k}v_{k}(for k=0,...,N), d_{k}=u_{k-1}u_{k}(for k=1,...,N), and f_{k}=v_{k-1}v_{k}(for k=1,...,N). - X(N): the X-cross of L(N), obtained by adding to L(N) one vertexw,
and four edges:
u
_{0}w, v_{N}w, v_{0}w, and u_{N}w. - Y(N): the Y-cross of L(N), obtained by adding a vertex w and three edges:
u
_{0}w, v_{N}w, and v_{0}w. - Z(N), the Z-cross of L(N), optained by adding the edge
u
_{0}v_{N}. - C(N), the C-cross of L(N), obtained by adding the edge
u
_{0}v_{0}. - A(N), the annulus, obtained from L(N) by adding the two edges
u
_{0}v_{0}u_{N}v_{N}.

N 0 1 L(N) ----o o----o---- ... | | | ... ----o o----0---- X(N) ----o. , o----o---- ... | o | | ... ----o' ` o----0---- Y(N) ----o. , o----o---- ... | o | | ... ----o' o----0---- Z(N) ----o , o----o---- ... | / | | ... ----o' o----0---- C(N) ----o----o----o---- ... | | | ... ----o o----0---- A(N) ----o----o----o---- ... | | | ... ----o----o----0----Recall that a tree T in a graph G is a connected subgraph with the same vertices as G, and with no cycle. The problem is to count the number of trees in these graphs. I use the graph symbol to denote the number of trees of a graph, as no confusion should arise.

These relations (with a complete proof) can be found in internet:

- L(N) = 4 L(N-1) - L(N-2)
- F(N) = 3 F(N-1) - F(N-2), which has solution F(N)=Fibinacci(2N)
- W(N) = W(N-1) + F(N) + F(N-1), which has solution W(N) = Lucas(2N) - 2

- Z(N) = L(N) + Z(N-1) + X(N-2) + Y(N-2)
- C(N) = L(N) + C(N-1) + X(N-2) + Y(N-2)
- Y(N) = L(N) + Y(N-1) + Z(N) + C(N)
- X(N) = Y(N) + 2 X(N-1) + Y(N-1)
- A(N) = A(N-1) + C(N-2) + 2 X(N-3) + Y(N-3)

These form a set of recursion relations that can be solved, starting with
the initial values

- L(0)=1, L(1)=4
- Z(0)=2, Z(1)=8
- C(0)=1, C(1)=7
- Y(0)=5, Y(1)=24
- X(0)=11, X(1)=45
- A(0)=1, A(1)=12

L C Z Y X A W F 1 1 1 2 5 8 1 1 3 2 4 7 8 24 45 12 5 8 3 15 35 36 110 224 74 16 21 4 56 160 161 487 1045 102 45 55 5 209 703 704 2103 4680 251 121 144 6 780 3015 3016 8914 20377 969 320 377

Notice that Z(N)=C(N)+1. This is clear from the recursion relations.
Can you show from the graphs which is the extra tree in Z(N) that is
not in C(N) ?

Another problem: what about the number of forests?

Marco Corvi - 2011