Crea sito
CONTING TREES


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:

Prove these other relations relating the number of trees of these graphs,


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