fact, parts of our analytical results have already been obtained in this context. However, we have obtained them independently by a direct enumeration technique which turned out to be quite similar to a counting lemma for bicolored trees that appeared in [@bollobright].

The main result on the structure of the remnant after iterated leaf removal when the graph is a large random graph of finite connectivity $\alpha$ is the following. The residue consists of $i(\alpha)N+O(1)$ isolated points and an induced subgraph without leaves or isolated points which we call the core. It contains $c(\alpha)N+O(1)$ vertices and $l(\alpha)N+O(1)$ edges. For $\alpha < e = 2.718\dots$, $c(\alpha)=l(\alpha)=0$ so the core is small. A second order phase transition occurs at $\alpha=e$ and for $\alpha >e$, $c(\alpha)$ and $l(\alpha)$ are $>0$. We shall argue that the core is made of a giant connected “core” component plus a finite number of small connected components involving a total of $o(N)$ vertices. The function $i(\alpha)$ is always non-vanishing, but it is non-analytic at $\alpha=e$.

The phase transition at $\alpha=e$ was found initially for the matching problem [@karpsipser; @pitteletal]. Physicists however have observed independently that some properties of random graphs are singular at $\alpha=e$ (see Ref. [@hartweig1] for 