FIG. 1. The Sierpinski carpet allows for disconnected borders, but they can be connected with no more with l · b links, so the number of possible borders grows no faster than an exponential with b , and the graph magnetizes. through the link from which the path first arrived at the vertex. With this algorithm, each link is crossed no more than twice, so the path is of no more than 2 z$_{Max}$b ; furthermore, all the links are crossed, so, since the boundary is connected, all the points are visited. As a consequence, all the spanning trees of b points starting from a vertex i can be constructed as paths of b − 1 , b, . . . , 2 z$_{Max}$b steps. Since each step can be chosen among at most z$_{Max}$ links, the total number of possible spanning trees, starting from i and made of b vertices, is less than and the thesis follows: When a vertex border is made of more disconnected parts, µ ( b ) grows exponentially if, for all borders, it’s possible to connect all the parts using no more than l · b vertices, where l is a constant of the graph: in fact in this case to each border of length b corresponds one connected vertex border of length between b and b · l , so that z b − 1 Max + z b Max + · · · + z 2 z$_{Max}$b Max = z 2 z$_{Max}$b +1 Max − z b − 1 Max z$_{Max}$ − 1 , N $^{p}$( b ) ≤ const · C $^{b}$. N ( b ) ≤ C b + C b +1 + · · · + C l · b = C l · b +1 − C b C − 1 . 11