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:
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:
These form a set of recursion relations that can be solved, starting with
the initial values
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