title: Random tree-weighted graphs
authors: Louigi Addario-Berry Jordan Barrett
text: 
  
   
  
  
  Department of Mathematics and Statistics, McGill University, Montréal, Canada
  louigi.addario@mcgill.ca
  jordan.barrett@mail.mcgill.ca
   
  http://problab.ca/louigi/
  
  
  [2010]Primary: 60C05, 05C80; Secondary: 05C05, 60F05 
  
  
   
  For each n ≥ 1, let ^n=(d^n(i),1 ≤ i ≤ n) be a sequence of positive integers with even sum ∑_i=1^n d^n(i) ≥ 2n. Let (G_n,T_n,Γ_n) be uniformly distributed over the set of simple graphs G_n with degree sequence ^n, endowed with a spanning tree T_n and rooted along an oriented edge Γ_n of G_n which is not an edge of T_n. Under a finite variance assumption on degrees in G_n, we show that, after rescaling, T_n converges in distribution to the Brownian continuum random tree as n →∞. Our main tool is a new version of Pitman's additive coalescent <cit.>, which can be used to build both random trees with a fixed degree sequence, and random tree-weighted graphs with a fixed degree sequence. As an input to the proof, we also derive a Poisson approximation theorem for the number of loops and multiple edges in the superposition of a fixed graph and a random graph with a given degree sequence sampled according to the configuration model; we find this to be of independent interest. 
  
  
  Random tree-weighted graphs
      Jordan Barrett
      August 27, 2020; revised January 22, 2021
  =============================================
  
  
  
  
  
  
  
  
  
  § INTRODUCTION
   
  
  By a rooted tree we mean a labeled tree t=((t),(t)), with a distinguished root node denoted r(t). 
  A tree-rooted graph is a pair (g,t,γ) where g=((g),(g)) is a labeled graph, t=((t),(t)) is a spanning tree of g, and γ=uv is a distinguished oriented edge with {u,v}∈(g)∖(t). We view t as a rooted tree by setting r(t)=u. 
  
  Throughout this work, we allow our graphs to have multiple edges and loops; in tree-rooted graphs, the root edge is allowed to be a loop. We say (g,t,γ) is simple if g is simple, i.e., if g contains no multiple edges or loops. 
  
  For a node u of a rooted tree t, we write c_t(u) for the number of children of u in t. Given a rooted tree t with (t)=[n]:={1,2,…,n}, the child sequence of t is the sequence _t=(c_t(i),1 ≤ i ≤ n). Similarly, given a tree-rooted graph (g,t,γ) with vertex set (g)=[n], the degree sequence of (g,t,γ) is the sequence (d_g(i),1 ≤ i ≤ n), where d_g(i) is the number of endpoints of edges incident to i in g; here loops are counted twice. 
  
  For any sequence =(d(1),…,d(n)) of non-negative integers, we define the degree distribution 
  p_=(p_(k),k ≥ 1) of  by letting p_(k) = #{i ∈ [n]: d(i)=k}/n. 
  
  The following theorem contains our main result, which is an invariance principle for the spanning trees in random tree-rooted graphs with a fixed degree sequence. To state it, two further pieces of notation are needed. Given a finite graph g=(v,e) and a constant c >0, we write cg for the measured metric space (v,,π) whose points are the elements of v, with (x,y):= c·_g(x,y), where _g(x,y) denotes graph distance in g, and with π the uniform probability measure on v. Also, for a sequence p=(p(k),k ≥ 1) of real numbers, we write μ_1(p):=∑_k≥ 1 kp(k) and μ_2(p):= ∑_k ≥ 1 k^2 p(k).
  
  For each n ≥ 1 let ^n=(d^n(i),1 ≤ i ≤ n) be a degree sequence with min_1 ≤ i ≤ n d^n(i) ≥ 1, with ∑_i ∈ [n] d^n(i) ≥ 2n and with ∑_i ∈ [n] d^n(i) even. Let p^n be the degree distribution of ^n. Suppose that there exists a probability distribution p=(p(k),k ≥ 1) such that (a) p^n → p pointwise and p(2)<1, and (b) μ_2(p^n) →μ_2(p) ∈ (0,∞). Then there exists σ=σ(p) ∈ (0,∞) such that the following holds. 
  
  For n ≥ 1 let (G_n,T_n,Γ_n) be chosen uniformly at random among all simple tree-rooted graphs with vertex set [n] and degree sequence  d^n. Then
  
      σ/n^1/2 T_n
  
  as n →∞ with respect to the Gromov-Hausdorff-Prokhorov topology, where  is the Brownian continuum random tree. 
  
  We refer the reader to <cit.> for a good discussion of the Gromov-Hausdorff-Prokhorov topology aimed at probabilists. 
  The technical insight underlying the proof of Theorem <ref> is the fact that  Pitman's additive coalescent <cit.> can be modified to yield a simple construction procedure for random tree-weighted graphs with a given degree sequence. We anticipate that this procedure has further interesting features to be explored. 
  
  
  
   §.§ Related work
  
  The enumerative combinatorics of tree-rooted maps was developed in the 1960's and 1970's <cit.>. The area has seen renewed attention over the last decade or so <cit.>. 
  Random tree-rooted maps can be interpreted as samples from a Fortuin-Kastelyn model at zero temperature, and are an active object of study in the planar probability community (see, e.g.,<cit.>). 
  
  There has also been some work on the typical number of spanning trees in uniformly random graphs <cit.> with given degree sequences. (In such models, the underlying graph is sampled uniformly at random from some set of allowed graphs; in our model, it is the tree-weighted graph which is uniformly random, which means the underlying measure on graphs is biased in favour of graphs with a greater number of spanning trees.) 
  
  Except in the setting of graphs on surfaces, we have not found any previous work on tree-weighted graphs, random or otherwise.
  
  
  
  
   §.§ Overview of the proof
  
  We begin with a small number of facts and definitions that are required for the overview. We say a sequence =(c(i),1 ≤ i ≤ n) of non-negative integers is a child sequence if it is the child sequence of some tree. Note that  is a child sequence if and only if ∑_1 ≤ i ≤ n c(i)=n-1, in which case 
  
      #{ t: _t=} 
      = n-1  c(1), … ,c(n) = 1/nn!/∏_i=1^n c(i)!  ;
  
  see <cit.>, Section 3.3.
   
  Given any sequence c=(c(i),1 ≤ i ≤ n) of non-negative integers, for k ≥ 1 we write Q_c(k) = #{i ∈ [n]: c(i)=k}. We call Q_c=(Q_c(k),k ≥ 0) the child statistics vector of . For a tree t with child sequence _t, we will  sometimes write Q_t=Q__t for succinctness. 
  
  Given a graph g, for an edge e ∈(g) we write m_g(e) for the multiplicity of edge e in g. Given a degree sequence =(d(1),…,d(n)), the classical configuration model <cit.> produces a random graph G such that 
  for any fixed graph g with degree sequence , 
  
      G=g∝1/∏_i=1^n 2^m_g(ii)∏_e ∈(g) m_g(e)!  .
  
  In Section <ref>, we define a sampling procedure, inspired by the configuration model and by Pitman's additive coalescent <cit.>, which produces a random tree-weighted graph (G,T,Γ) with the property that for any fixed tree-weighted graph (g,t,γ) with degree sequence , 
  
      (G,T,Γ)=(g,t,γ)∝2^γ is a loop· m_g-t(γ)/∏_i=1^n 2^m_g-t(ii)·∏_e ∈(g) m_g-t(e)!  ,
  
  where g-t is the graph with the same vertex set as g and with edge multiplicities given by
  
      m_g-t(e) = 
      				m_g(e)	    e ∉(t) 
      
      				m_g(e)-1   e ∈(t)  .
  
  
  We call a random tree-weighted graph (G,T,Γ) with distribution given by (<ref>) a random tree-weighted graph with degree sequence . Note that in this case, conditionally given that G is simple, (G,T,Γ) is uniformly distributed over simple tree-rooted graphs with degree sequence .
  
  The sampling procedure we use has enough exchangeability that, conditional on its child sequence, the resulting spanning tree T is uniformly distributed; that is, for any fixed child sequence =(c(i),1 ≤ i ≤ n), and any tree t with _t=, 
  
      T=t_T= = n-1  
      c(1),…,c(n)^-1  .
  
  
  Now let (^n,n ≥ 1) be a sequence of degree sequences satisfying the conditions of Theorem <ref>; for each n let (G(^n),T(^n),Γ(^n)) be a random tree-weighted graph with degree sequence ^n. 
  We prove (see Proposition <ref>) that 
  there is a probability distribution q=(q(i),i ≥ 0) with μ_2(q)<∞ such that the child statistics vector Q_T(^n) satisfies that
  n^-1Q_T(^n)() → q() in probability for all ≥ 0, and moreover that μ_2(n^-1Q_T(^n)) →μ_2(q) in probability. It then follows from a result of Broutin and Marckert <cit.> that 
  
      σ/n^1/2 T(^n)
  
  in the Gromov-Hausdorff-Prokhorov sense, where σ^2 = μ_2(q)-1 and  is the Brownian continuum random tree.
  
  This is not quite the convergence claimed in Theorem <ref>, because 
  (G(^n),T(^n),Γ(^n)) is a random tree-weighted graph with degree sequence ^n, whereas Theorem <ref> concerns random simple tree-weighted graphs. To obtain Theorem <ref> from (<ref>), we show that there is α∈ (0,1] such that as n →∞, 
  
      G(^n)T(^n)→α
  
  in probability. The value of (<ref>), informally, is that it implies that conditioning G(^n) to be simple has an asymptotically negligible effect on the law of T(^n). Since the law of (G(^n),T(^n),Γ(^n)), conditional on the simplicity of G(^n), is uniform over simple tree-weighted graphs with degree sequence ^n, we can then conclude straightforwardly. 
  
  We finish the overview with a brief discussion of how we prove (<ref>).
  Our procedure for constructing random tree-weighted graphs with a given degree sequence first constructs the tree T(^n), then randomly pairs the remaining half-edges as in the standard configuration model. Viewing T(^n) as fixed, this leads us to the following more general question. Let G=(V,E) be a random graph with a given degree sequence generated according to the configuration model, and let T=(V,E') be a fixed, simple graph with the same vertex set. What is the probability that the union of G and T forms a simple graph (i.e. that G is a simple graph and that E and E' are disjoint)? We provide a partial answer to this question by proving a fairly general Poisson approximation theorem for the number of loops and multiple edges in the superposition of a fixed graph and a random graph drawn from the configuration model (see Theorem <ref>). 
  In order to apply Theorem <ref>, we need that the joint degree statistics in G(^n) and in T(^n)) are sufficiently well-behaved; proving this is the task of Section <ref>. We then state and prove Theorem <ref> in Section <ref>, and finally put all the pieces together to prove Theorem <ref> in Section <ref>.
  
  
  
  
  
  § PITMAN'S ADDITIVE COALESCENT WITH A FIXED DEGREE SEQUENCE
  
  
  
  
   §.§ The sampling process
  
  Let =(d(1),…,d(n)) be a degree sequence, which is to say that d(1),…,d(n) are non-negative integers. 
  To be well-defined, the next process requires that ∑_1 ≤ i ≤ n d(i) ≥ 2n-1 and that d(i) ≥ 1 for all 1 ≤ i ≤ n. 
  
  [style=thmbox]
  Pitman's additive coalescent.
  The process has n-1 steps, and at the start of step k consists of a rooted forest F_k()={T_1^k(),…,T_n+1-k^k()} with n+1-k trees. At the start of step 1, these trees are isolated vertices with labels 1,…,n.  Vertex i has d(i) half-edges (i1,i2,…,id(i)) attached to it, and id(i) is distinguished as the root half-edge.
  
  Step k: 
  
  Choose a uniformly random pair (r_k,s_k), where r_k is a root half-edge which is not paired in F_k() and s_k is a non-root half-edge which is not paired in F_k() and additionally belongs to a different tree of F_k() from r_k. 
  
  Pair the half-edges r_k and s_k to create an edge e_k connecting their endpoints; this merges two trees of F_k(). 
  The root of the new tree is the same as the root of the tree of F_k() containing s_k. In the new tree, the vertex incident to r_k is the child of the vertex incident to s_k. 
  
  Define F_k+1() to be the forest consisting of the new tree thus created, together with the remaining n-k-1 unaltered trees of F_k(). 
  
  
  
  
  An example is shown in Figure <ref>.
  Write T() = T^n_1() for the single tree in the random forest F_n(). Attached to the tree T() there is a single pendant (unpaired) root half-edge which is incident to the root of T(), and if ∑_i=1^n d(i) > 2n-1 then there are also other pendant half-edges. By ignoring pendant half-edges, we may view T() as a random rooted tree with vertex set [n]. 
  
  It will be useful to additionally define two edge labellings of T(), denoted  and . We define (e) to be the step at which edge e was added; so (e_k):= k. We define (e) to be the non-root half-edge used in creating e; so  (e_k)=s_k. Note that  is a bijection between (T()) and [n-1]. Also, if i ∈ [n] has c_T()(i)=c, then  assigns c distinct half-edges from the set {i1,…,i(d(i)-1)} to the edges between i and its children in T(). 
  
  We use the phrase “execution path” to mean a sequence of pairs (r_1,s_1),…,(r_n-1,s_n-1) which may concievably appear as the ordered sequence of pairs of half-edges added during the course of Pitman's coalescent. 
  
  The next proposition fully describes the joint distribution of T(), , and . 
  In its proof, and in what follows, for a rooted tree t and a node u ∈(t)∖{r(t)} we write (u) for the parent of u in t. Also, we use the falling factorial notation (k)_ℓ:=k(k-1)·…· (k-ℓ+1)=k!/(k-ℓ)!. 
   
  Let =(d(1),…,d(n)) be a degree sequence with d(i) ≥ 1 for all i ∈ [n] and with ∑_i=1^n d(i) ≥ 2(n-1), and write m=1/2∑_i=1^n d(i). (Note: we allow that ∑_i=1^n d(i) is odd.) Then the following properties all hold. 
  
  
    * For any fixed rooted tree t with vertex set [n], 
  
      T()=t = 
      1/(2m-n)_n-1∏_i=1^n (d(i)-1)_c_t(i)  .
  
  
    * Fix any set ⊂⋃_i=1^n {i1,…,i(d(i)-1)} with ||=n-1. 
  Conditionally given that {s_1,…,s_n-1}=, the triple 
  (T(),,) is uniformly distributed over the ((n-1)!)^2  triples which are consistent with the event {s_1,…,s_n-1}=. 
  
    * The sequence (s_1,…,s_n-1) of non-root half-edges, added by Pitman's coalescent, is uniformly distributed over the set of sequences of (n-1) distinct elements of ⋃_1 ≤ i ≤ n{i1,…,i(d(i)-1)}. Consequently, {s_1,…,s_n-1} is a uniformly random size-(n-1) subset of ⋃_1 ≤ i ≤ n{i1,…,i(d(i)-1)}. 
  
    * Finally, conditionally given that T()=t and given the set {s_1,…,s_n-1} of non-root half-edges added by Pitman's coalescent, the ordering (e_1,…,e_n-1) of (t) is uniformly distributed over the (n-1)! possible orderings of (t). 
  
  
  
  At step i of the process, there are n+1-i components and 2m-n+1-i unpaired non-root half-edges. We may specify the pair (r_i,s_i) by first revealing the non-root half-edge s_i, then revealing r_i. Whatever the choice of s_i, there are n-i possibilities for r_i, so the number of distinct choices for the pair (r_i,s_i) is (2m-n+1-i) (n-i). 
  Thus, the total number of possible execution paths for the process is 
  
      ∏_i=1^n-1 (2m-n+1-i) (n-i) = (n-1)! (2m-n)_n-1.
  
  
  The execution path followed by the process is uniquely determined by the tree T() and the functions :(T()) → [n-1] and :(T()) →⋃_i=1^n {i1,…,i(_i-1)}. To see this, fix any k ∈ [n-1]. Then the edge e_k created at step k of Pitman's coalescent may be recovered as e_k = ^-1(k); and, if e_k=uv with v=(u) then the half-edges paired to create e_k are the root half-edge vd(v) incident to v and the half-edge ^-1(e_k). 
  
  Now, fix any tree t with degree sequence , any bijection k:(t) → [n-1], and any function h:(t) → which, for all i ∈ [n], assigns c_t(i) distinct values from the set {1,…,(d(i)-1)} to the edges between i and its children in t. Together with (<ref>), the observation of the preceding paragraph implies that 
  
      T()=t,=k,=h = 1/(n-1)! (2m-n)_n-1  .
  
  
  Having fixed the tree t, the number of possible values for  is (n-1)! and the number of possible values for  is ∏_i ∈ [n] (d(i)-1)_c_t(i). It follows that 
  
      T()=t = (n-1)!·∏_i ∈ [n] (d(i)-1)_c_t(i)/(n-1)! (2m-n)_n-1 = 
      ∏_i ∈ [n] (d(i)-1)_c_t(i)/(2m-n)_n-1  ,
  
  which proves the first claim of the proposition. 
  
  Next, fix  as in the second assertion of the proposition, 
  and any ordering of  as (h_1,…,h_n-1). Then the number of execution paths which yield that s_k=h_k for k ∈ [n-1] is precisely (n-1)!. To see this, note that if s_j=h_j for 1 ≤ j ≤ k then, whatever the choices of the root half-edges (r_j,1 ≤ j ≤ k), the forest F^n_k has n+1-k component trees so there are n-k unpaired root half-edges in components different from that of s_k; any such root half-edge may be chosen as r_k. Since there are also (n-1)! possible orderings of , the second assertion of the proposition follows. 
  
  To prove the third statement, fix a set  and an ordering (h_1,…,h_n-1) of its elements, as in the previous paragraph. 
  For each 1 ≤ k < n-1, given that s_j=h_j for 1 ≤ j < k, whatever the choices of (r_j,1 ≤ j < k) may be, there are n-k ways to choose r_k in a distinct tree from h_k. It follows that there are ∏_k=1^n-2 (n-k) = (n-1)! execution paths with the property that s_k=h_k for each 1 ≤ k ≤ n-1. 
  Since this number does not depend on , it follows that each size-(n-1) subset of ⋃_1 ≤ i ≤ n{i1,…,i(d(i)-1)} is equally likely. 
  
  Finally, fix both the tree t and an unordered set 
   of non-root half-edges with |∩{i1,…,i(d(i)-1)}|=c_t(i) for all i ∈ [n]. We consider the number of execution paths which yield T()=t and {s_1,…,s_n-1}=. The number of choices of an ordering function k:(t) → [n-1] consistent with these constraints is still (n-1)!. Moreover, whatever the choice of k, under the further constraint =k, the number of possibilities for  is ∏_i ∈ [n] c_t(i)!. To see this, note that for each i ∈ [n], the constraints precisely imply that   ∩{i1,…,i(d(i)-1)}={s_1,…,s_n-1}∩{i1,…,i(d(i)-1)}, and  is fixed once we additionally specify which of these c_t(i) half-edges is matched to which child of i, for each i ∈ [n]. It follows that the number of execution paths which yield that T()=t, that =k and that {s_1,…,s_n}= is 
  
      ∏_i=1^n c_t(i)!  .
  
  As this quantity doesn't depend on the choice of the ordering function k, the final assertion of the proposition follows. 
  
  
  We state a corollary of the above proposition, for later use. 
  
  The tree T() is a uniformly random rooted tree with child sequence _T.
  
  The corollary follows since the formula for T()=t from Proposition <ref>  only depends on t through _t. 
  
  We now assume that ∑_i=1^n d(i) ≥ 2n and that ∑_i=1^n d(i) is even, and define a random tree-rooted graph (G,T,Γ)=(G(),T(),Γ()) as follows: First, let T=T() be the random tree built by Pitman's coalescent, and let Γ^+=Γ^+() be its root half-edge. We refer to T as the spanning tree-elect of a to-be-constructed tree-rooted graph. 
  Next, choose a uniformly random matching of the 2m-2(n-1) pendant half-edges attached to T, and pair the half-edges according to this matching to create G=G(). Then let  Γ be the edge containing Γ^+, oriented so that Γ^+ is at the head; for later use, let Γ^-=Γ^-() be the other half-edge of Γ. We call (G(),T(),Γ()), or any other graph with the same distribution, a random tree-rooted graph with degree sequence . The tree T has now taken office. 
  
  The next proposition describes the distribution of (G(),T(),Γ()).  For a tree-rooted graph (g,t,γ), 
  
  Let =(d(1),…,d(n)) be a degree sequence with d(i) ≥ 1 for all i ∈ [n], and write m=1/2∑_i=1^n d(i). 
  Fix a tree-rooted graph (g,t,γ) where g is a graph with degree sequence . Then
  
      (G(),T(),Γ())=(g,t,γ)∝2^γ is a loop· m_g-t(γ)/∏_i=1^n 2^m_g-t(ii)·∏_e ∈(g) m_g-t(e)!  .
  
  
  
  Proposition <ref> gives us a formula for T()=t. We next focus on computing 
  
      G()=gT()=t.
   
  Write r for the root of t, and γ=qr for the oriented root edge of g. 
  Given that T()=t, each i ∈ [n] with i  r(t) has d'(i):=d(i)-c_t(i)-1 pendant half-edges attached to it, and r has d'(r) := d(r)-c_t(r) half-edges attached to it. Conditionally given that T()=t, the graph G()-T() is distributed as CM('), a random graph with degree sequence '=(d'(1),…,d'(n)) sampled according to the configuration model, so with distribution as in (<ref>)), and more 
  Writing m':=m-(n-1)=1/2∑_i=1^n d'(i) and g'=((g),(g)∖(t)), it follows that
  
      G()=gT()=t    = CM(') = g'
          = 
      2^m'(m')!/(2m')!∏_i=1^n d'(i)!/∏_i=1^n 2^m_g'(ii)·∏_e ∈(g') m_g'(e)!
          = 2^m'(m')!/(2m')!∏_i=1^n d'(i)!/∏_i=1^n 2^m_g-t(ii)·∏_e ∈(g) m_g-t(e)!  .
   
  For the second equality we have used the exact expression for the distribution of CM('), which can be found in, e.g., <cit.>, equation  (7.2.6). 
  For the last equality, we use that m_g'(ii)=m_g-t(ii) since t is a tree so contains no loops, and that m_g'(e)=m_g-t(e) by definition when e ∈(g'). 
  
  Given that T()=t and that G()=g, in order to have (G(),T(),Γ())=(g,t,γ) it is necessary and sufficient that Γ()=γ. This occurs precisely if γ^+, the half-edge of γ incident to r, was matched with some half-edge incident to q. Since the matching of half-edges in G()-T() is chosen uniformly at random, by symmetry the conditional probability that this occurred is m_g-t(γ)/d'(r) if γ is not a loop, and is 2m_g-t(γ)/d'(r) if γ is a loop. We may unify these two formulas by writing
  
      Γ()=γT()=t,G()=g = 
      2^γ is a loopm_g-t(γ)/d'(r).
  
  Combined with the formula for T()=t from Proposition <ref>,  this gives 
  
      (G(),T(),Γ())=(g,t,γ)
          = 
      1/(2m-n)_n-1∏_i=1^n (d(i)-1)_c_t(i)
           ·2^m'(m')!/(2m')!∏_i=1^n d'(i)!/∏_i=1^n 2^m_g-t(ii)·∏_e ∈(g) m_g-t(e)!
             ·2^γ is a loopm_g-t(γ)/d'(r)
          = ∏_i=1^n (d(i)-1)! ·2^m-(n-1)(m-(n-1))!/2m'(2m-n)!·2^γ is a loopm_g-t(γ)/∏_i=1^n 2^m_g-t(ii)·∏_e ∈(g) m_g-t(e)!  .
  
  In the second equality we have used that (2m-n)_n-1(2m')!=2m'(2m-n)!, that (d(i)-1)_c_t(i)d'(i)! = (d(i)-1)! for i  r, and that (d(r)-1)_c_t(r)d'(r)! = d'(r) (d(r)-1)!. The first two terms on the final line do not depend on the triple (g,t,γ), so the result follows. 
  
  
  
  
  § CONCENTRATION OF DEGREES
  
  
  Throughout this section, let (^n,n ≥ 1) be a sequence of degree sequences satisfying the conditions of Theorem <ref>, and also let p^n and p be as in Theorem <ref>. Next, for n ≥ 1 let T(^n) be the tree built by Pitman's additive coalescent applied to the degree sequence ^n=(d^n(i),1 ≤ i ≤ n). Let ^n=(c^n(i),1 ≤ i ≤ n) be the child sequence of T(^n), and recall that  Q_^n=(Q_^n(a),a ≥ 0) is the child statistics vector of ^n. Also, for 0 ≤ a < b, let P^n_, = #{1 ≤ i ≤ n: d^n(i)=,c^n(i)=}. Finally, let ρ := 1/(μ_1(p)-1). Note that 
  since ∑_i ∈ [n] d^n(i) ≥ 2n, necessarily μ_1(p^n) ≥ 2; since p^n → p pointwise and μ_2(p^n) →μ_2(p), it follows that μ_1(p^n) →μ_1(p), so μ_1(p) ≥ 2 and hence ρ∈ (0,1].
   
  For ≥ 0 let 
  
      q() := ∑_=+1^∞ p()·Bin(-1,)=.
  
  Then μ_2(q) < ∞ and μ_2(n^-1Q_^n) →μ_2(q) in probability as n →∞. Moreover, for all 0 ≤ <, n^-1P^n_, p()·Bin(-1,)=, and n^-1Q_^n()  q(), in both cases as n →∞. 
  
  Let (G(^n),T(^n),Γ(^n)) be a random tree-weighted graph with degree sequence ^n. Using Proposition <ref>, together with existing results from the literature,  it is fairly straightforward to establish that (σ n^-1/2)T(^n), with σ=μ_2(q)-1 ∈ (0,∞), where  is the Brownian continuum random tree. However, in order to show that such convergence holds for the corresponding random simple tree-weighted graphs, we additionally need the next proposition, which establishes that the number of pairs of tree-adjacent vertices  in T(^n) with given fixed degrees is well-concentrated around its expected values. This will be used in order to show that the probability of G(^n) being simple given T(^n) asymptotically behaves like a constant.
  
  Write G_-(^n) = G(^n)-T(^n) and let _-^n=(d^n_-(i),1 ≤ i ≤ n) be the degree sequence of G_-(^n). For integers k,ℓ≥ 0, let 
  
      α(k,ℓ) = 
      ∑__1,_2 ≥ 0_2p(ℓ+_2+1)Bin(ℓ+_2,ρ)=_2· p(k+_1+1)Bin(k+_1,ρ)=_1  .
   
  
  For integers k,ℓ≥ 0 let 
  
      A^n(k,ℓ) = 
      |{uv ∈(T(^n)) : ^n_-(u)=k,^n_-(v)=ℓ}|.
   
  Then for all k,ℓ≥ 0, 
  
      1/nA^n(k,ℓ) α(k,ℓ)
  
  as n →∞, and also 
  
      1/n∑_k,ℓ≥ 0 
      kℓ A^n(k,ℓ) ∑_k,ℓ≥ 0 kℓα(k,ℓ).
  
  
  The proofs of Propositions <ref> and <ref> appear in Appendix <ref>. 
  
  To conclude the section, we observe that α(k,ℓ) defines a probability distribution on pairs of non-negative integers. Indeed, 
  
      ∑_k ≥ 0∑__1 ≥ 0 
      p(k+_1+1)Bin(k+_1,ρ)=_1    = 
      ∑_m≥ 0∑_a=0^m
      p(m+1)Bin(m,ρ)=
          = ∑_m ≥ 0 p(m+1) = 1-p(0)=1  ,
  
  and 
  
      ∑_ℓ≥ 0∑__2 ≥ 0_2p(ℓ+_2+1)Bin(ℓ+_2,ρ)=_2
          = 
      ∑_m ≥ 0∑_a=0^m
       p(m+1) Bin(m,ρ)=
          = ∑_m ≥ 0 p(m+1) · m ρ 
      =  (μ_1(p)-(1-p(0)))ρ = (μ_1(p)-1)ρ = 1,
  
  so by factorizing ∑_k,ℓ≥ 0α(k,ℓ) we obtain 
  
      ∑_k,ℓ≥ 0α(k,ℓ) 
      =
      ∑_m ≥ 0 p(m+1)·∑_m ≥ 0∑_m ≥ 0  p(m+1) · m ρ 
      = 1  ;
   
  the fact that ∑_k,ℓ≥ 0α(k,ℓ)=1 will be used in the proof of Proposition <ref>. 
  A similar computation shows that 
  
      ∑_k,ℓ≥ 0 kℓ·α(k, ℓ) 
      ≤∑_m ≥ 0 mp(m+1)·∑_m ≥ 0 m^2 p(m+1) ρ 
      = μ_2(p)-2μ_1(p) +1 < ∞  ,
   
  a fact we will use in bounding the probability of simplicity of G(^n). 
  
  
  
  § POISSON APPROXIMATION FOR GRAPH SUPERPOSITIONS.
  
  In this section we state a Poisson approximation theorem for the number of loops and multiple edges in the superposition of a fixed simple graph and a random graph with a fixed degree sequence; this in particular allows us to control the probability that such a superposition yields a simple graph. 
  
  Let H be a simple graph with vertex set v(H)=[n]. 
  Fix a degree sequence =(d(1),…,d(n)) whose sum of degrees is even, and let G be a random graph with degree sequence  sampled according to the configuration model.
  For vertices u,v ∈ [n] and i ∈ [d(u)],j ∈ [d(v)], let ui,vj be the indicator of the event that half-edge ui is matched with half-edge vj in G. Now write 
  
      = (G) = {(ui,uj): u ∈ [n], i,j ∈ [d(u)], i<j}
          = (G,H) 
      = {((ui_1,vj_1),(ui_2,vj_2)): u,v ∈ [n], uv ∉ e(H), 
                                   i_1,i_2 ∈ [d(u)], j_1,j_2 ∈ [d(v)], u<v, i_1<i_2,j_1 ≠ j_2 },  and
          = (G,H) = {(ui,vj): uv ∈ e(H), i ∈ [d(u)], j ∈ [d(v)] },
    
  and let
  
      L 	    = L(G) = ∑_(ui,uj) ∈ui,uj  ,
       
      M 	    = M(G,H) = ∑_((ui_1,vj_1),(ui_2vj_2)) ∈(ui_1,vj_1)(ui_2vj_2)  ,  and
       
      N	    = N(G,H) ∑_(ui,vj) ∈ui,vj .
   
  Note that the graph with edge set e(G)∪ e(H) is simple precisely if L+M+N=0.
  
   
  Fix a sequence of simple graphs (h_n,n ≥ 1) with v(h_n)=[n] for all n ≥ 1 and max_v ∈ [n]{_h_n(v)} = o(n). For each n ≥ 1 let ^n=(d^n(v),1 ≤ v ≤ n) be a degree sequence and let p^n be the degree distribution of ^n. 
  Suppose that there exists a probability distribution p=(p(k),k ≥ 0) with μ_2(p) ∈ [0,∞) and p(0)<1 such that the following holds.
  
  First, p^n → p pointwise and μ_2(p^n) →μ_2(p). Second, there are non-negative numbers (α(a,b),a,b ≥ 0) such that for any a,b ≥ 0
  
      α^n(a,b) := 1/n|{uv ∈ e(h_n) : d^n(u)=a,d^n(v)=b }| →α(a,b),
  
  and 
  
      ∑_k,ℓ≥ 0 klα^n(k,ℓ) →∑_k,ℓ≥ 0 klα(k,ℓ) < ∞
  
  
  For n ≥ 1 let G_n be distributed according to the configuration model on graphs with vertex set [n] and degree sequence  d^n. 
  Then with L_n=L(G_n), M_n=M(G_n,h_n) and N_n=N(G_n,h_n), we have
  
      Dist(L_n,M_n,N_n) - Poi(ν/2)⊗Poi(ν^2/4)⊗Poi(η)_TV→ 0
  
  as n →∞, where ν = (μ_2(p)/μ_1(p)) - 1 and 
  η = 1/μ_1(p)∑_i,j ≥ 1 ijα(i,j). 
  
  In the statement of Theorem <ref> we have introduced the notation _h_n(v) for the degree of vertex v in h_n, and the notation μ-ν_TV for the total variation distance between probability measures. The proof of Theorem <ref> appears in Appendix <ref>. This theorem has the following consequence for random tree-weighted graphs, which we will use in the next section. 
  
  Let (^n,n ≥ 1) and (p^n,n ≥ 1) be as in  Theorem <ref>, and for n ≥ 1 let (G(^n),T(^n),Γ(^n)) be a random tree-weighted graph with degree sequence . Then
  
      G(^n) simpleT(^n)exp(-ν/2-ν^2/4-η)  ,
  
   as n →∞. 
  
  This corollary follows straightforwardly from Theorem <ref> when μ_2(p^n)>2, in which case G_-(^n)=G(^n)-T(^n) has a linear number of edges. However, when μ_2(p^n)=2, and the graph G_-(^n) has a sub-linear number of edges a separate argument is needed. The proof of Corollary <ref> also appears in Appendix <ref>.
  
  
  
  § PROOF OF THEOREM <REF>
  
   
  Let (^n,n ≥ 1) be a sequence of degree sequences satisfying the conditions of Theorem <ref>.  For n ≥ 1 let T(^n) be the tree built by Pitman's additive coalescent applied to degree sequence ^n, and let ^n be the child sequence of T(^n). By Proposition <ref> (1), conditionally given ^n, the tree T(^n) is uniformly distributed over the set of trees with child sequence ^n. 
  
  By Proposition <ref>, the child statistics vectors (Q_^n,n ≥ 1) satisfy that, as n →∞, for all a ≥ 0, 
  
      n^-1Q_^n(a)  q(a),
  
  and moreover that μ_2(n^-1Q_^n(a)) →μ_2(q). Here q=(q(a),a ≥ 0) is as in Proposition <ref>, and in particular satisfies μ_2(q) <∞. We will also need that μ_2(q) > 1, and we now justify this. 
  
  The convergence (<ref>) and the 
  fact that μ_2(n^-1Q_^n(a)) →μ_2(q) together imply that μ_1(n^-1Q_^n(a)) →μ_1(q). But μ_1(n^-1Q_^n(a)) = (n-1)/n since Q_^n is a child sequence, so necessarily μ_1(q)=1. By the definition of q, 
  if ρ = 1 then q(1)=p(2), and p(2) < 1 by  assumption. If ρ > 1 then 
  
      q(0) := ∑_=1^∞ p()·Bin(-1,)=0 > 0,
  
   so again q(1) ≤ (1-q(0))< 1. Thus, we always have q(1)<1, which together with the fact that μ_1(q)=1 implies that μ_2(q)>1. 
   
  
  Writing σ=μ_2(q)-1 ∈ (0,∞), it then follows by Theorem 1 of <cit.> that 
  
      T(^n):=
      σ/n^1/2 T(^n) ,
  
  in the Gromov-Hausdorff-Prokhorov sense.[Theorem 1 of <cit.> is stated for plane trees with a fixed degree sequence, rather than labeled trees with a fixed degree sequence. However, as noted by Broutin and Marckert <cit.>, a straightforward combinatorial argument shows that the same result holds for labeled trees. Also, as stated, the theorem only yields convergence in the Gromov-Hausdorff sense; but the proof proceeds by establishing convergence distributional of coding functions. As explained in <cit.>, such proofs immediately yield the stronger Gromov-Hausdorff-Prokhorov convergence.]
  
  We aim to prove the same statement with T(^n) replaced by T_n:=(σ/n^1/2)T_n, where (G_n,T_n,Γ_n) is is a uniformly random simple tree-rooted graph with degree sequence ^n. To accomplish this, we use that the law of (G_n,T_n,Γ_n) is precisely the conditional law of (G(^n),T(^n),Γ(^n)) given that G(^n) is a simple graph. 
  
  
  Writing 𝕂 for Gromov-Hausdorff-Prokhorov space as in <cit.>, for any bounded continuous function f:𝕂→ we have 
  
      f(T(^n))·G(^n) simple    =
      (𝐄(f(T(^n))·G(^n) simple | T(^n))) 
          = f(T(^n))·G(^n) simpleT(^n).
  
  Since f(T(^n))→f(), and G(^n) simpleT(^n)exp(-ν/2-ν^2/4-η) by Corollary <ref>, 
  it follows that 
  
      f(T(^n))·G(^n) simple→exp(-ν/2-ν^2/4-η) f().
  
  Furthermore, 
  
      G(^n) simple = G(^n) simpleT(^n)→exp(-ν/2-ν^2/4-η),
  
  and therefore 
  
      𝐄(f(T(^n)) | G(^n) simple)
      = 
      f(T(^n))·G(^n) simple/G(^n) simple→f()  .
  
  Since 
  
      f(T_n) = f(T(^n) | G(^n) simple  ,
  
  the fact that T_n now follows by the Portmanteau theorem. 
  
  
  
  
  § PROOFS OF PROPOSITIONS <REF> AND <REF>
  
  
  Before beginning the proofs in earnest, we
  state and prove a simple bound on the asymptotic behaviour of maximum degrees and sums of small sets of degrees, for sequences of degree sequences as in Theorems <ref> and <ref>, which will be used multiple times below. 
  
  For each n ≥ 1 let ^n=(d^n(v),1 ≤ v ≤ n) be a degree sequence and let p^n be the degree distribution of ^n. 
  Suppose that there exists a probability distribution p=(p(k),k ≥ 0) such that p^n → p pointwise and μ_2(p^n) →μ_2(p) ∈ [0,∞). Then max_1 ≤ i ≤ n d^n(i) = o(n^1/2). 
  Also, for any sets (A_n,n ≥ 1) with A_n ⊂ [n] and |A_n|=o(n), it holds that ∑_i ∈ A_n d^n(i)=o(n).
  
  
  If p^n → p pointwise and μ_2(p^n) →μ_2(p) ∈ [0,∞), then for all > 0 there is M such that 
  
      lim inf_n →∞∑_k=1^M k^2p^n(k) ≥μ_2(p) - ,
  
  so sup_M ≥ 1lim inf_n →∞∑_k=1^M k^2p^n(k) ≥μ_2(p). 
  If additionally there is δ > 0 such that max_1 ≤ i ≤ n d^n(i) ≥δ n^1/2 for infinitely many n, then 
  
      lim sup_n →∞μ_2(p^n) ≥δ^2 + sup_M ≥ 1lim inf_n →∞∑_k=1^M k^2p^n(k) > μ_2(p),
  
  so μ_2(p^n) ↛μ_2(p).
  
  Similarly, for sets (A_n,n≥ 1) as in the statement, since |A_n|=o(n), for any M ∈ we have ∑_i ∈ A_n^n (d^n(i))^2d^n(i)≤ M = o(n), so for any > 0 there is M ∈ such that 
  
      lim inf_n →∞1/n∑_i=1^n (d^n(i))^2d^n(i)≤ Mi ∉A_n≥μ_2(p) - .
  
  This implies that lim inf_n →∞ n^-1∑_i=1^n (d^n(i))^2i ∉A_n≥μ_2(p). 
  If also there is δ > 0 such that ∑_i ∈ A_n (d^n(i))^2 > δ n for infinitely many n, then 
  
      lim sup_n →∞μ_2(p^n)=lim sup_n →∞1/n∑_i=1^n (d^n(i))^2 ≥μ_1(p)+δ  ,
  
  so μ_2(p^n) ↛μ_2(p). 
  
  Note that the conditions on the degree sequences in both Theorem <ref> and Theorem <ref> allow Fact <ref> to be applied. 
  
  To prove Proposition <ref>, we will  make use of the following lemma, which uses the second moment method to control how subsampling affects degree distributions. The proof of the proposition immediately follows that of the lemma. 
  
  For any integer ≥ 1 there exists n_0 such that for all n ≥ n_0 the following holds. 
  Let = (d(1),…,d(n)) be a degree sequence with d(i) ≥ 1 for all i∈ [n] and with  ∑_i =1^n d(i) ≥ 2n-1,  set S = ⋃_i=1^n {i1,…,i(d(i)-1)} and write s=|S|. Let  be a uniformly random subset of S with |U|=n-1, and for 1 ≤ i ≤ n write U_i = #{1 ≤ j < d(i): (i,j) ∈}. 
  For 0 ≤ <, write P_, = #{1 ≤ i ≤ n: (d(i),U_i)=(,)}. 
  Then for all > 0, 
  
      |P_, -  P_,| >  P_, < 1/^21/ P_b,a+ 2^2/s  .
  
  
  
  We fix 0 ≤≤ and compute the first and second moments of P_+1,; this makes the calculations slightly easier to read than they would be for P_,. 
  
  Fix indices k and ℓ with k ≠ℓ and d(k)=d(ℓ)=+1. 
  Since  is a uniformly random subset of S, by symmetry we have 
  
      |U_k|= = |U_ℓ|= = ·s- n-1-s  n-1^-1,
  
  and 
  
      |U_k|=|U_ℓ|= = ^2 ·s-2 n-1-2s  n-1^-1,
  
  so writing n_+1 = #{1 ≤ i ≤ n: d(i) = +1}, we have 
  
      P_+1, = n_+1·s- n-1-s  n-1^-1
  
  and
  
      P_+1,
         
      = n_+1(n_+1-1) ^2 s - 2 n-1-2s  n-1^-1-s- n-1-^2s  n-1^-2
          
      + n_b+1b  as-b  n-1-1s  n-1^-1
      - b  a^2 s-b  n-1-1^2s  n-1^-2,
  
  where the final line accounts for the diagonal terms. 
  Bounding the final line from above by P_b+1,a and cancelling terms in the parenthetical expression in the middle line gives 
  
      P_+1,- P_b+1,a
         ≤  n_+1(n_+1-1) ^2 
      (n-1)_2(s-(n-1))_2(-)/(s)_2- (n-1)_^2(s-(n-1))_-^2/(s)_^2.
  
  The ratio of the first and the second term in the final parentheses is 
  
      (n-1)_2/(n-1)_^2(s-(n-1))_2(-)/(s-(n-1))_-^2(s)_^2/(s)_2   ≤(s)_^2/(s)_2≤1+/s-2^≤ 1 + 2^2/s  ,
  
  the last bound holding for  fixed and s large. This gives 
  
      P_+1,   ≤ P_b+1,a + n_+1(n_+1-1) ^2 2^2/ss- n-1-^2s  n-1^-2
          <  P_b+1,a + 2^2/s ( P_+1,)^2  ,
  
  and the lemma follows by Chebyshev's inequality. 
  
  
  We first bound μ_2(q) by writing 
  
      μ_2(q)     = ∑_≥ 0^2 q() 
          = ∑_≥ 0^2 ∑_ >  p()·Bin(-1,)=
         ≤∑_ > 0^2 p()·∑_0 ≤ < Bin(-1,)=
          = μ_2(p)^2 < ∞  .
  
  
  Next, since p^n → p pointwise and μ_2(p^n) →μ_2(p) < ∞, for any > 0 there is k such that 
  ∑_d ≥ k d^2 p^n(d) < and ∑_d ≥ k d^2 p(d) <. 
  If node i has  children in T(^n) then d^n(i) ≥ a+1, so it follows that 
  
      ∑_ = k^∞^2 Q_^n()/n    = ∑_≥ k∑_ >^2 #{i ≤ n: c^n(i)=,d^n(i)=}/n
         ≤∑_ > k^2 ∑_ < #{i ≤ n: c^n(i)=,d^n(i)=}/n
          = ∑_ > k^2 p^n() <   .
  
  To complete the proof it thus suffices to show that 
  n^-1P^n_,→ p()·Bin(-1,)= in probability for all 0 ≤ < and that n^-1Q_^n→ q pointwise in probability; the fact that μ_2(n^-1Q_^n) →μ_2(q) in probability then immediately follows. 
  
  By the third statement of Proposition <ref>, the set of non-root half-edges in T(^n) is a uniformly random size-(n-1) subset of the set S^n:= ⋃_1 ≤ i ≤ n{i1,…,i(d^n(i)-1)}. We will apply Lemma <ref> to control the numbers of nodes with a given number of children in T(^n). To make the coming applications of that lemma transparent, we write s^n := |S^n| = ∑_1 ≤ i ≤ n (d^n(i)-1).
  
  
  We handle the cases μ_1(p)=2 and μ_1(p) > 2 separately. If μ_1(p)=2 then |S^n| = ∑_1 ≤ i ≤ n (d^n(i)-1) = (1+o(1)) n as n →∞. Note that in this case ρ(p)=1/(μ_1(p)-1)=1 so q()=p(+1) for all ≥ 0. 
  For any ≥ 0, by (<ref>) we then have 
  
      P^n_+1, = (1-o(1)) np^n(+1)  |S^n|-1- n-1 -|S_n| n-1^-1 = (1-o(1)) np^n(+1).
  
  If p(a+1) > 0 then n p^n(a+1) = Θ(n), so
  
      1/P^n_a+1,a + 2(a+1)^2/|S^n| = o(1),
   
  and hence by Lemma <ref>, 
  
      P^n_+1,/n p(+1)= q().
  
  If p(a+1)=0 then p^n(a+1) = o(1), so P^n_a+1,a/n → 0 and thus P^n_+1,/n  0=q() by Markov's inequality. Since this holds for all a ≥ 0, and ∑_≥ 0 P^n_+1,/n ≤ 1=∑_a ≥ 0 q(a), it follows that ∑_≥ 0 P^n_+1,/n → 1 in probability. 
  This implies that ∑_ > +1 P^n_,/n → 0 in probability, 
  so 
  
      Q_^n()/n = 1/n∑_ >  P^n_, = P^n_+1,/n + ∑_ > +1P^n_,/n q()  ,
  
  and that for all > +1, 
  P^n_,/n → 0=p(b)·Bin(b-1,)=a in probability, as required.
  
  
  We now assume μ_1(p)>2, so that ρ(p)=1/(μ_1(p)-1)<1. 
  Since p=(p_k,k ≥ 1) is supported on the positive integers, 
  
      ∑_≥ 0 q() = ∑_≥ 0∑_=+1^∞ p()Bin(-1,)=
       = 
      ∑_≥ 1 p()=1  .
  
  Recalling that Q_^n() = ∑_ >  P^n_,, 
  to show that n^-1Q_^n() → q() in probability, it therefore suffices to prove that 
  P^n_+1,/n → p(+1)·Bin(,)= for all 0 ≤≤, and we now turn to this. 
  
  Since μ_1(p^n) →μ_1(p), it follows that 
  |∑_i=1^n d^n(i) - μ_1(p) n| = n|μ_1(p^n)-μ_1(p)| = o(n) as n →∞, so s^n = (1+o(1))n(μ_1(p)-1). Thus, for any ≥ 1 and 0 ≤≤ we have 
  
      ·s^n- n-1-s^n  n-1^-1    = (n-1)_(s^n-(n-1))_-/(s^n)_
          = (1-o(1))n^ ((μ_1(p)-2)n)^-/((μ_1(p)-1) n)^
          = (1-o(1))(μ_1(p)-2)^-/(μ_1(p)-1)^
          = (1-o(1))Bin(,)=.
  
  Using (<ref>) we thus have 
  
      P^n_+1, = (1-o(1)) np^n(+1) 
      Bin(,)=
      =(1-o(1)) np(+1) 
      Bin(,)=  ,
  
  so again, applying Lemma <ref> in the case that p(b+1)>0, and applying Markov's inequality in the case that p(b+1)=0, we obtain that, as n →∞, 
  
      P^n_+1,/n p(+1)Bin(,)=  ,
  
  as required.
  
  We now turn to controlling the joint degrees of pairs of tree-adjacent vertices in tree-weighted graphs. 
  Given a degree sequence =(d(1),…,d(n)) and a tree t with (t)=[n], 
  for integers _1,_2,_1,_2 let 
  
      R__1,_2,_1,_2(t,) 
          = #{u ∈(t)∖{r(t)}: d(u)=_1, d((u))=_2, c_t(u)=_1, c_t((u))=_2}
          = ∑_u ∈(t)∖{r(t)}d(u)=_1,c_t(u)=_1·d((u))=_2,c_t((u))=_2  .
  
  If (g,t,γ) is a tree-rooted graph and g has degree sequence , then  
  R__1,_2,_1,_2(t,) counts the number of edges xy of t with y=(x) such that c_t(x)=_1, c_t(y)=_2 and d_g(x)=_1, d_g(y)=_2. 
   
  
  Under the assumptions of Theorem <ref>, 
  for any integers 0 ≤_1 < _1 and 0 ≤_2 < _2, as n →∞, 
  
      R__1,_2,_1,_2(T(^n),^n)/n→_2 p(_2)Bin(_2-1,)=_2· p(_1)Bin(_1-1,)=_1
  
  in probability, where ρ=1/(μ_1(p)-1). 
  We introduce two pieces of notation before beginning the proof. For a half-edge h we write v(h) for the vertex incident to h. Also, for r ∈ we write r_+ := max(r,0). 
  
  First, if _2=0 then the right-hand side is zero, and also R__1,_2,_1,_2(T(^n),^n)=0, since if  v=(u) ∈ T(^n) then c_T(^n)(v) ≥ 1. The result thus holds trivially when _2=0, and we assume hereafter that _2 ≥ 1. For the remainder of the proof we write R__1,_2,_1,_2=R__1,_2,_1,_2(T(^n),^n) for succinctness. 
  
  Let  be a fixed, size-(n-1) subset of S^n := ⋃_1 ≤ i ≤ n{i1,…,i(d^n(i)-1)}. 
  Write ^n={s_1,…,s_n-1} for the (unordered) set of non-root half-edges of T(^n).
  We now show that for any half edge h ∈ and any root half-edge r with v(r) ≠ v(h), for all 1 ≤ i ≤ n-1, 
  
      (r_i,s_i)=(r,h) | ^n= = (r_1,s_1)=(r,h) | ^n=  .
  
  To see this, note that by the second assertion of Proposition <ref>, the number of execution paths with ^n= is ((n-1)!)^2. We claim that for any i ∈ [n-1], the number of execution paths with ^n= which additionally satisfy that (r_i,s_i)=(r,h) is ((n-2)!)^2. As this number does not depend on i ∈ [n-1], the displayed identity follows from this claim. 
  
  To prove the claim, simply note that there are (n-2)! possible orderings of  consistent with the constraint that s_i=h. Having fixed such an ordering (h_1,…,h_n-1), for each j ∈ [n-1] with j  i, if s_k=h_k for 1 ≤ k < j then, excluding r_i there are n-j-j<i unpaired root half-edges in components different from that of s_j, and any such root half-edge may be chosen as r_j. Thus the number of execution paths with ^n= and such that (r_i,s_i)=(r,h) is (n-2)! ·∏_j ∈ [n-1]∖{i}(n-j-j < i) = ((n-2)!)^2. 
  
  
  
  Now fix a second non-root half-edge h'  h and a second root half-edge r' r not incident to the same vertex as h'. 
  Then a similar argument to the one leading to (<ref>) shows that that for any 1 ≤ i < j ≤ n, 
  
      (r_i,s_i)=(r,h),(r_j,s_j)=(r',s') | ^n=
          = (r_1,s_1)=(r,h),(r_2,s_2)=(r',s') | ^n=  .
  
  In the current case, the number of execution paths leading to the events in both the left- and right-hand probabilities is ((n-3)!)^2. 
  
  We will next use the above identities in order to perform first and second moment computations. 
  For any set H ⊂ S^n, for 0 ≤ <
  let V^n_,(H) = {i ∈ [n]: d^n(i)=, |H ∩{i1,…,i(d^n(i)-1)|=}. Note that V^n_,(^n) is simply the set of nodes with degree  in G(^n) and with a children in T(^n); so  P^n_,=|V^n_,(^n)|. 
  
  Fix a non-root node u ∈ T(^n), and let m∈ [n-1] be such that e_m = {(u),u}. Then v(r_m)=u and v(s_m)=(u), so u ∈ R__1,_2,_1,_2 if and only if v(r_m) ∈ V^n__1,_1(^n) and v(s_m)∈ V^n__2,_2(^n). 
  By (<ref>), it follows that 
  
      R__1,_2,_1,_2 | ^n=
          = (n-1) v(r_1) ∈ V^n__1,_1(^n), v(s_1) ∈ V^n__2,_2(^n) | ^n=.
  
  Likewise, by (<ref>) it follows that
  
      R__1,_2,_1,_2 2 | ^n=
          = n-1  2v(r_1),v(r_2) ∈ V^n__1,_1(^n),v(s_1),v(s_2) ∈ V^n__2,_2(^n) | ^n=.
  
  We develop the latter two identities in turn.
  
  For integers 0 ≤ <, the number of non-root half-edges h ∈^n with v(h) ∈ V^n_,(^n) is · |V^n_,(^n)|, and the number of root half-edges h with v(h)∈ V^n_,(^n) is just |V^n_,(^n)|. 
  Conditionally given that ^n=, the half-edge s_1 is a uniformly random element of , so
  
      v(s_1) ∈ V^n__2,_2(^n) | ^n= = _2|V^n__2,_2()|/|| = _2|V^n__2,_2()|/n-1  .
  
  Having chosen s_1, if v(s_1)=v then v(r_1) is a uniformly random element of [n]∖{v}, so 
  
      v(r_1) ∈ V^n__1,_1(^n) | ^n=,v(s_1) ∈ V^n__2,_2(^n)
      = (|V^n__1,_1()|-(_1,_1)=(_2,_2))_+/n-1.
  
  Using these two identities in  (<ref>), it follows that 
  
      (n-1)R__1,_2,_1,_2 | ^n=
      = _2|V^n__2,_2()|(|V^n__1,_1()|-(_1,_1)=(_2,_2))_+  ,
  
  so since |V^n_,(^n)|=P^n_, for all 0 ≤ <, by Proposition <ref> we have 
  
      R__1,_2,_1,_2/n | ^n   = 1/n(n-1)_2 P^n__2,_2(P^n__1,_1-(_1,_1)=(_2,_2))
      
         _2 p(_2)Bin(_2-1,)=_2· p(_1)Bin(_1-1,)=_1  .
  
  
  For the second moment calculation, we need to additionally compute 
  
      v(r_2) ∈ V^n__1,_1(^n),v(s_2) ∈ V^n__2,_2(^n) | ^n=,
      v(r_1) ∈ V^n__1,_1(^n), v(s_1) ∈ V^n__2,_2(^n)  .
  
  Under the conditioning in (<ref>), the number of non-root half-edges h ∈^n∖{s_1} with v(h) ∈ V^n__2,_2() is (_2· |V^n__2,_2()|-1)_+, so 
  
      v(s_2) ∈ V^n__2,_2(^n) | ^n=,
      v(r_1) ∈ V^n__1,_1(^n), v(s_1) ∈ V^n__2,_2(^n)
      
          = (_2· |V^n__2,_2()|-1)_+/n-2  .
  
  Now suppose 
  that ^n=,
  v(r_1) ∈ V^n__1,_1(^n), v(s_1) ∈ V^n__2,_2(^n), and 
  that v(s_2) ∈ V^n__2,_2(), and consider the number of possible values for r_2. We claim that the number of unpaired root half-edges h with v(h) ∈ V^n__1,_1(^n) such that v(h) is in a component different from v(s_2) is 
  
      (|V^n__1,_1()|-1-(_1,_1)=(_2,_2))_+.
   
  To see this, note that if (_1,_1)=(_2,_2) and 
  either v(s_2)=v(s_1) or v(s_2)=v(r_1), then we are precisely constrained constrained to choose h so that v(h) ∈ V^n__1,_1()∖{v(r_1),v(s_1)}. On the other hand, if (_1,_1)=(_2,_2) and v(s_2) ∉{v(r_1),v(s_1)} then we are constrained to choose h so that v(h) ∈ V^n__1,_1()∖{v(r_1),v(s_2)}. Both cases agree with the above formula. When  (_1,_1)=(_2,_2), the claim is straightforward, since in that case we are only constrained to choose h so that v(h) ∈ V^n__1,_1()∖{v(r_1)}. 
  It follows that 
  
      v(r_2) ∈ V^n__1,_1(^n) | ^n=,
      v(s_2) ∈ V^n__2,_2(^n), v(r_1) ∈ V^n__1,_1(^n), v(s_1) ∈ V^n__2,_2(^n)
      
          = 
      (|V^n__1,_1()|-1-(_1,_1)=(_2,_2))_+/n-2  .
  
  Combining the above identities with (<ref>) yields that 
  
      2(n-1)(n-2) R__1,_2,_1,_2 2 | ^n=
          = _2|V^n__2,_2()|(_2|V^n__2,_2()|-1)_+
      
         ·(|V^n__1,_1()|-(_1,_1)=(_2,_2))_+
      (|V^n__1,_1()|-1-(_1,_1)=(_2,_2))_+,
  
  so since _2 ≥ 1, Proposition <ref> implies that
  
      R__1,_2,_1,_2(R__1,_2,_1,_2-1)/n^2 | ^n
          = _2 P^n__2,_2(_2 P^n__2,_2-1)_+/n(n-1)·(P^n__1,_1-(_1,_1)=(_2,_2))_+
      (P^n__1,_1-1-(_1,_1)=(_2,_2))_+/n(n-2)
         (_2 p(_2)Bin(_2-1,)=_2· p(_1)Bin(_1-1,)=_1)^2  .
  
  Also, (<ref>) implies that n^-2R__1,_2,_1,_2 | ^n 0, which with the preceding asymptotic implies that 
  
      R__1,_2,_1,_2^2/n^2 | ^n(_2 p(_2)Bin(_2-1,)=_2· p(_1)Bin(_1-1,)=_1)^2  .
  
  Combining this with (<ref>) gives that 
  
      R__1,_2,_1,_2/n^2 | ^n
      -
      R__1,_2,_1,_2/n | ^n^2  0  ;
  
  the conditional Chebyshev's inequality then gives that for all > 0, 
  
      |R__1,_2,_1,_2/n-R__1,_2,_1,_2/n | ^n|> | ^n 0.
  
  Taking expectations on the left of the previous inequality to remove the conditioning, and again using (<ref>), this time to replace the term R__1,_2,_1,_2/n | ^n in the probability by the constant C:=_2 p(_2)Bin(_2-1,)=_2· p(_1)Bin(_1-1,)=_1, we obtain that 
  
      |R__1,_2,_1,_2/n-C|>→ 0,
  
  as required. 
  
  
  We may reexpress A^n(k,ℓ) as
  
      A^n(k,ℓ) 
          = 
      ∑__1,_2 ≥ 0∑_u∈(T(^n))r(T(^n)) ∉{u,(u)}
                         ·^n(u)=k+_1+1,^n(u)=_1
                         ·^n((u))=ℓ+_2+1,
      ^n((u))=_2
          + 
      ∑__1,_2 ≥ 0∑_u∈(T(^n))(u)=r(T(^n))
                         ·^n(u)=k+_1 + 1,^n(u)=_1
                         ·^n((u))=ℓ+_2,
      ^n((u))=_2
  
  For fixed _1,_2 ≥ 0, 
  if we replace r(T(^n)) ∉{u,(u)} by u  r(T(^n)) in the first double sum, then the inner sum is simply R_k+_1+1,ℓ+_2+1,_1,_2. It follows that 
  
      A^n(k,ℓ) 
          = 
      ∑__1,_2 ≥ 0 
      R_k+_1+1,ℓ+_2+1,_1,_2
          + 
      ∑__1,_2 ≥ 0∑_u∈(T(^n))(u)=r(T(^n))
                         ·^n(u)=k+_1 + 1,^n(u)=_1
                         ·^n((u))=ℓ+_2,
      ^n((u))=_2
          - 
      ∑__1,_2 ≥ 0∑_u∈(T(^n))(u)=r(T(^n))
                         ·^n(u)=k+_1+1,^n(u)=_1
                         ·^n((u))=ℓ+_2+1,
      ^n((u))=_2  .
  
  But each of the last two double sums is bounded by c^n(r(T(^n))), since they both count each child of the root at most once. Under the assumptions of Theorem <ref>, by Fact <ref> we have c^n(r(T(^n))) ≤max_1 ≤ i ≤ n d^n(i) = o(n^1/2),
   so the preceding identity gives
  
      |A^n(k,ℓ) 
       -
      ∑__1,_2 ≥ 0 
      R_k+_1+1,ℓ+_2+1,_1,_2|=o(n^1/2).
  
  Since 
  
      n^-1
      R_k+_1+1,ℓ+_2+1,_1,_2
      
         _2p(ℓ+_2+1)Bin(ℓ+_2,ρ)=_2· p(k+_1+1)Bin(k+_1,ρ)=_1
  
  by Proposition <ref>, and summing the right-hand side of the last expression over a_1,a_2 ≥ 0 gives α(k,l), it follows that for any > 0, 
  
      A^n(k,l)/n ≥α(k,l)-→ 1.
  
  But also n^-1∑_k,l ≥ 0 A^n(k,l) = |(T(^n))| = (n-1)/n → 1; so since ∑_k,l≥ 0α(k,l)=1, we must in fact have that
  
      A^n(k,l)/nα(k,l)
  
  for all k,l ≥ 0, as required. 
  
  It remains to show that n^-1∑_k,l ≥ 0 kl A^n(k,l) ∑_k,l≥ 0 klα(k,l). 
  For this we will exploit the exchangeability of Pitman's additive coalescent. Recall the notation v(h) for the vertex incident to half-edge h. 
  Note that for any M ∈ we have 
  
      ∑_k,l≥ 0 klA^n(k,l) - ∑_0 ≤ k,l≤ M klA^n(k,l) 
          = ∑_uv ∈ e(T^n) d^n_-(u)d^n_-(v) max(d^n_-(u),d^n_-(v)) > M
         ≤∑_uv ∈ e(T^n) d^n(u)d^n(v) max(d^n(u),d^n(v)) > M
          = 
      ∑_i=1^n-1 d^n(v(r_i))d^n(v(s_i)) max(d^n(v(r_i)),d^n(v(s_i))) > M.
  
  Now, by Proposition <ref> (3) and the identity (<ref>),  for any 1 ≤ i ≤ n-1 we have 
  
      d^n(v(r_i))d^n(v(s_i)) max(d^n(v(r_i)),d^n(v(s_i))) > M
          = d^n(v(r_1))d^n(v(s_1)) max(d^n(v(r_1)),d^n(v(s_1))) > M,
  
  and by the definition of Pitman's additive coalescent we have 
  
      d^n(v(r_1))d^n(v(s_1))max(d^n(v(r_1)),d^n(v(s_1))) > M
          = 
      ∑_u ∈ [n]∑_v ∈ [n]
      d^n(u)d^n(v)max(d^n(u),d^n(v))) > Mv(s_1)=u,v(r_1)=v
          = 
      ∑_u ∈ [n]∑_v ∈ [n]
      d^n(u)d^n(v)max(d^n(u),d^n(v)) > M·d^n(u)/nμ_1(p^n)·1/n-1  ,
  
  where we have used that ∑_i ∈ [n] d^n(i)=nμ_1(p^n). Next, 
  
      ∑_u ∈ [n]∑_v ∈ [n]
      (d^n(u))^2d^n(v)max(d^n(u),d^n(v)) > M
         ≤(∑_u ∈ [n]: d^n(u)>M (d^n(u))^2)·∑_v ∈ [n] d^n(v) + 
      (∑_v ∈ [n]:d^n(v) > M d^n(v)) ·∑_u ∈ [n] (d^n(u))^2  ,
          = nμ_1(p^n)·∑_u ∈ [n]: d^n(u)>M (d^n(u))^2 +  n μ_2(p^n)·∑_v ∈ [n]:d^n(v) > M d^n(v)  .
  
  Since p^n → p, μ_1(p^n) →μ_1(p) and μ_2(p_n) →μ_2(p), for any δ > 0 we may choose M=M(δ) sufficiently large so that
  ∑_u ∈ [n]: d^n(u)>M(d^n(u))^2 < δ n and ∑_v ∈ [n]:d^n(v) > M d^n(v) < δ n, for all n ≥ 1. For such M, the previous bound and the two identities which precede it yield that 
  
      ∑_k,l≥ 0 klA^n(k,l) - ∑_0 ≤ k,l≤ M klA^n(k,l) ≤1/μ_1(p^n) (δ n μ_1(p^n) + δ n μ_2(p^n)).
  
  By Markov's inequality, it follows that for all > 0 there is M ∈ such that for all n ∈, 
  
      ∑_k,l≥ 0 klA^n(k,l) - ∑_0 ≤ k,l≤ M klA^n(k,l) >  n < .
  
  Finally, since n^-1A^n(k,l) α(k,l), it follows that for all M ∈ we have 
  
      1/n∑_0 ≤ k,l≤ M klA^n(k,l) ∑_0 ≤ k,l≤ M klα(k,l)  ,
   
  so the preceding probability bound implies that 
  
      1/n∑_k,l≥ 0 klA^n(k,l) lim_M →∞∑_0 ≤ k,l ≤ M klα(k,l) = ∑_k,l ≥ 0 klα(k,l)  ,
  
  as required. 
  
  
  
  
  § PROOF OF THEOREM <REF>
   
  Let H be a simple graph with vertex set v(H)=[n], and let G be a random graph with degree sequence =(d(1),…,d(n)) sampled according to the configuration model. Recall the definitions of (G),(G,H),(G,H) and L(G),M(G,H),N(G,H) from Section <ref>. 
  The first subsection will provide a quantitative approximation result for mixed moments of L,M and N. In the second subsection, we will use this approximation to prove Theorem <ref>. 
  
  
  
  
   §.§ Deterministic bounds on loops and multi-edges
   
  Our arguments in this section are based on and fairly closely parallel those from <cit.>. 
  We recall the falling factorial notation (x)_ℓ = x(x-1) … (x-ℓ+1). In what follows, it is convenient to  define (x)_ℓ = 1 if ℓ = 0, and (x)_ℓ = 0 if ℓ < 0. 
  
   
  Write m = 1/2∑_i=1^n d(i), and write d_max = max{d(1),…,d(n)}. For any positive integers q,r,s ∈,
  
      |(L)_q(M)_r(N)_s - (||)_q(||)_r(||)_s/∏_i=0^q+2r+s-1 2m - 1 - 2i|
      ≤
      C(S_1+S_2)
  
  where C is a constant depending only on q,r and s, S_1 is defined by the following identity,
  
      S_1 ∏_i=0^q+2r+s-1 (2m - 1 - 2i)
      =   
      (||)_q-2(||)_r(||)_s ∑_1 ≤ u ≤ n d(u)^3
         +
      (||)_q-1(||)_r-1(||)_s ∑_1 ≤ u ≠ v ≤ n d(u)^3 d(v)^2
         +
      (||)_q-1(||)_r(||)_s-1∑_uv ∈ e(H) d(u)^2 d(v)
         +
      (||)_q(||)_r-2(||)_s∑_1 ≤ u ≤ n 
       u ∉{v_1, v_2} d(u)^3 d(v_1)^2 d(v_2)^2
         +
      (||)_q(||)_r-1(||)_s-1∑_1 ≤ u, v_1, v_2 ≤ n 
       u,v_1,v_2 distinct
       uv_2 ∈ e(H) d(u)^2 d(v_1)^2 d(v_2)
         +
      (||)_q(||)_r(||)_s-2∑_uv_1,uv_2 ∈ e(H) 
       v_1 ≠ v_2 d(u) d(v_1) d(v_2),
  
  and S_2 is defined by
  
      S_2
         =
      (||)_q(||)_s∑_k=1^r-1 (||)_r-k∑_ℓ = 0^k d_max^2ℓ∏_i=0^q+2r+s-1-(2k-ℓ)1/2m-1-2i.
  
   
  
  Throughout the proof, write
  
      (x,y,z)
      =
      ( (x_1,…,x_q),(y_1,…,y_r),(z_1,…,z_s))
      ∈^q ×^r ×^s
  
  to denote a generic element of ^q ×^r ×^s. For (x,y,z) ∈^q ×^r ×^s, write
  
      x = ∏_i=1^qx_i,
            y = ∏_i=1^ry_i,
             z = ∏_i=1^sz_i.
  
  We say (x,y,z) is non-repeating if x_1,x_2, … ,x_q are pairwise distinct, y_1,y_2, … ,y_r are pairwise distinct, and z_1,z_2, … ,z_s are pairwise distinct. In what follows, write
  
      := ∑_(x,y,z) ∈^q ×^r ×^s(x,y,z)  is non-repeating,
  
  and, for S ⊂^q ×^r ×^s, write
  
      _S := ∑_(x,y,z) ∈ S(x,y,z)  is non-repeating.
  
  Note that (L)_q(M)_r(N)_s =  xyz, so 
  
      (L)_q(M)_r(N)_s =  xyz = 1.
  
  
  We say (x,y,z) is non-conflicting if the 2q+4r+2s half-edges appearing in x,y and z are pairwise distinct, and otherwise we say (x,y,z) is conflicting. Since half-edges in G are paired uniformly at random, for non-conflicting (x,y,z) we have
  
      xyz=1
      =
      ∏_i=0^q+2r+s-11/2m - 1 - 2i.
  
  
  Now, for a given (x,y,z), let er(x,y,z) be defined as follows:
  
      er(x,y,z) 
      :=
      xyz = 1 - ∏_i=0^q+2r+s-11/2m - 1 - 2i.
  
  By (<ref>), if (x,y,z) is non-conflicting then er(x,y,z)=0, so
  
      (L)_q(M)_r(N)_s   =
      ∏_i=0^q+2r+s-11/2m - 1 - 2i
      +
      er(x,y,z)
         =
      (||)_q(||)_r(||)_s/∏_i=0^q+2r+s-1 2m - 1 - 2i
      +
      _(x,y,z)  is conflicting er(x,y,z).
  
  By the triangle inequality this implies
  
      | (L)_q(M)_r(N)_s - (||)_q(||)_r(||)_s/∏_i=0^q+2r+s-1 2m - 1 - 2i| ≤_(x,y,z)  is conflicting| er(x,y,z) |.
  
  To bound the error terms, we must make a distinction between two types of conflicts. This distinction is most easily understood by way of an example. On the one hand, suppose x_1 = (ui,uj_1) and x_2 = (ui,uj_2) for u ∈ V(G) and distinct i,j_1,j_2 ∈ [d(u)]. Then x_1x_2 = 1 is the event that the half edge ui is joined to uj_1 and uj_2 simultaneously, and x_1x_2 = 1=0. On the other hand, suppose y_1 = (ui_1,vj_1),(ui_2,vj_2) and y_2 = (ui_1,vj_1),(ui_3,vj_3) for distinct u,v ∈ V(G), distinct i_1,i_2,i_3 ∈ [d(u)], and distinct j_1,j_2,j_3 ∈ [d(v)]. Then y_1y_2 = 1 is the event that u and v are connected by a triple edge, and y_1y_2 = 1 > 0. 
  
  We say a conflicting triple (x,y,z) is a bad conflict if xyz=1=0, and otherwise we say (x,y,z) is a good conflict. In the above examples, the first is a bad conflict and the second is a good conflict. Let =  (q,r,s) ⊆^q ×^r ×^s and =  (q,r,s) ⊆^q ×^r ×^s be the collections of bad conflicts and good conflicts respectively. The rest of this proof is dedicated to bounding ||,||, and er(x,y,z) for (x,y,z) ∈∪. 
  
  (Bounding ||): 
  If (x,y,z) is a bad conflict then one of the following must hold (in reading the below descriptions, it may be useful to consult Figure <ref>):
  
  
  
    * There exists 1 ≤ a < b ≤ q, u ∈ V(G) and distinct i_1,i_2,i_3 ∈ [d(u)] such that x_a = (ui_1,ui_2) and x_b = (ui_1,ui_3). Write _xx for the set of (x,y,z) ∈ that contain a pair (x_a,x_b) of this form. 
  
  
    * There exists 1 ≤ a ≤ q, 1≤ b ≤ r, distinct u,v ∈ V(G), distinct i_1,i_2,i_3 ∈ [d(u)], and distinct j_1,j_2 ∈ [d(v)] such that x_a = (ui_1,ui_3) and y_b = (ui_1,vj_1),(ui_2,vj_2). Write _xy for the set of (x,y,z) ∈ that contain a pair (x_a,y_b) of this form.
  
  
    * There exists 1 ≤ a ≤ q, 1≤ b ≤ s, uv ∈ e(H), distinct i_1,i_2 ∈ [d(u)], and j ∈ [d(v)] such that x_a = (ui_1,ui_2) and z_b = (ui_1,vj). Write _xz for the set of (x,y,z) ∈ that contain a pair (x_a,z_b) of this form.
  
  
    * There exists 1 ≤ a < b ≤ r, distinct u,v_1,v_2 ∈ V(G), distinct i_1,i_2,i_3 ∈ [d(u)], distinct j_1,j_2 ∈ [d(v_1)], and distinct k_1,k_2 ∈ [d(v_2)] such that y_a = (ui_1,v_1j_1),(ui_2,v_1j_2) and y_b = (ui_1,v_2k_1),(ui_3,v_2k_2). Write _yy for the set of (x,y,z) ∈ that contain a pair (y_a,y_b) of this form.
  
  
    * There exists 1 ≤ a ≤ r, 1 ≤ b ≤ s and distinct u,v_1,v_2 ∈ V(G) such that uv_2 ∈ e(H), distinct i_1,i_2 ∈ [d(u)], distinct j_1,j_2 ∈ [d(v_1)], and k ∈ [d(v_2)] such that y_a = (ui_1,v_1j_1),(ui_2,v_1j_2) and z_b = (ui_1,v_2k). Write _yz for the set of (x,y,z) ∈ that contain a pair (y_a,z_b) of this form.
  
  
    * There exists 1 ≤ a < b ≤ s, distinct uv_1,uv_2 ∈ e(H), i ∈ [d(u)], j ∈ [d(v_1)], and k ∈ [d(v_2)] such that z_a = (ui,v_1j) and z_b = (ui,v_2k). Write _zz for the set of (x,y,z) ∈ that contain a pair (z_a,z_b) of this form.
  
  
  We next turn to bounding the sizes of each set, starting with _xx. The number of choices for a and b is q(q-1)/2. Having chosen these, for each possible choice of u ∈ V(G), there are less than d(u)^3 choices for i_1,i_2 and i_3. Then, having chosen these, we must choose one of i_1,i_2 and i_3 to be repeated in x_a and x_b. Lastly, we must choose the remaining q-2 entries for x, r entries for y, and s entries for z. Hence,
  
      |_xx|
         ≤
      (||)_q-2(||)_r(||)_s q(q-1)/2 ∑_1 ≤ u ≤ n 3 d(u)^3
         =
      C_1 (||)_q-2(||)_r(||)_s ∑_1 ≤ u ≤ n d(u)^3,
  
  where C_1 = C_1(q) = 3q(q-1)/2. Note that _xx is empty if q ≤ 1, so |_xx| = 0. In this case the right hand side is also zero by our convention that (k)_ℓ = 0 for ℓ<0. Therefore, the bound also holds for q≤ 1. The subsequent bounds can likewise be seen to hold when the right hand side is zero, though we do not explicitly verify this in every case.
  
  When building an element of _xy, the number of ways to choose a and b is qr. Having chosen these, for each pair u,v ∈ V(G), there are less than d(u)^3 d(v)^2 choices for i_1,i_2,i_3 ∈ [d(u)] and j_1,j_2 ∈ [d(v)]. Then, there are a constant number of ways to arrange the half-edges in x_a and y_b. Lastly, we must choose the remaining entries for x,y and z. Hence,
  
      |_xy|
         ≤ 
      C_2 (||)_q-1(||)_r-1(||)_s ∑_1 ≤ u ≠ v ≤ n d(u)^3 d(v)^2,
  
  where C_2 depends only on q and r.
  
  For an element of _xz, for each uv ∈ e(H), there are less than d(u)^2 d(v) ways to choose i_1,i_2 ∈ [d(u)] and j ∈ [d(v)]. Hence,
  
      |_xz|
         ≤
      C_3(||)_q-1(||)_r(||)_s-1∑_uv ∈ e(H) d(u)^2 d(v).
  
  For _yy, for each u,v_1,v_2 ∈ V(G), there are less than d(u)^3 d(v_1)^2 d(v_2)^2 ways to choose i_1,i_2,i_3 ∈ [d(u)], j_1,j_2 ∈ [d(v_1)], and k_1,k_2 ∈ [d(v_2)]. Hence,
  
      |_yy|
         ≤
      C_4 (||)_q(||)_r-2(||)_s∑_1 ≤ u, v_1, v_2 ≤ n 
       u,v_1,v_2  distinct d(u)^3 d(v_1)^2 d(v_2)^2.
  
  For _yz, for each u,v_1,v_2 ∈ V(G) such that uv_2 ∈ e(H), there are less than d(u)^2 d(v_1)^2 d(v_2) ways to choose i_1,i_2 ∈ [d(u)], j_1,j_2 ∈ [d(v_1)], and k ∈ [d(v_2)]. Hence,
  
      |_yz|
         ≤
      C_5 (||)_q(||)_r-1(||)_s-1∑_1 ≤ u, v_1, v_2 ≤ n 
       u,v_1,v_2  distinct
       uv_2 ∈ e(H) d(u)^2 d(v_1)^2 d(v_2).
  
  Lastly, for _zz, for each uv_1,uv_2 ∈ e(H), there are less than d(u) d(v_1) d(v_2) ways to choose i ∈ [d(u)], j ∈ [d(v_1)] and k ∈ [d(v_2)]. Hence,
  
      |_zz|
         ≤
      C_6 (||)_q(||)_r(||)_s-2∑_uv_1,uv_2 ∈ e(H) 
       v_1 ≠ v_2 d(u) d(v_1) d(v_2).
  
  Note that the values of C_1,C_2,C_3,C_4,C_5 and C_6 depend only on q,r and s.
  
  (Bounding |er(x,y,z)| for (x,y,z) ∈): If (x,y,z) ∈ then xyz=1=0, meaning 
  
      |er(x,y,z)|
      =
      ∏_i=0^q+2r+s-11/2m - 1 - 2i
  
  
  (Bounding ||): Suppose (x,y,z) ∈. Then (x,y,z) is conflicting, meaning a half-edge appears more than once in x ∪ y ∪ z. However, since xyz = 1 > 0 for (x,y,z) ∈, it cannot be the case where xyz contains the event that a half-edge is paired to two different half-edges simultaneously. Hence, there must be a half-edge pair that appears more than once in x ∪ y ∪ z. Furthermore, this half-edge pair must appear more than once in y, since the edges in y and z are disjoint. It follows that any (x,y,z) ∈ can be constructed in the following way:
  
  
    * Choose x and z arbitrarily. The number of choices here is (||)_q(||)_s.
  
    * Choose a set of indices 1 ≤ a_1 < a_2 <  … < a_k ≤ r and arbitrarily choose the elements y_a ∈ y such that a ≠ a_i for all 1 ≤ i ≤ k. The number of choices here is (||)_r-k times a constant in terms of r.
  
    * Choose 1 ≤ b_1 ≤…≤ b_ℓ≤ r such that {b_1, … ,b_ℓ}⊆{a_1, … ,a_k}. For each 1 ≤ i ≤ℓ, build y_b_i by choosing a half-edge pair already in y, then choosing the other half-edge pair arbitrarily. The number of choices for each i is less than d_max^2 times a constant in terms of r. 
  
    * For each a ∈{a_1, … ,a_k}∖{b_1 … ,b_ℓ}, build y_a by choosing two half-edge pairs already in y. The number of choices here is a constant in terms of r.
  
  Since every element of  can be constructed in this way, we get
  
      ||
         ≤
      C(r) (||)_q(||)_s∑_k=1^r-1 (||)_r-k∑_ℓ = 0^k d_max^2ℓ.
  
  
  (Bounding er(x,y,z) for (x,y,z) ∈):
  Let (x,y,z) ∈ and suppose we can construct (x,y,z) as above with a particular k and ℓ. Then there are 2k - ℓ half-edge pairs that are redundant when calculating xyz=1. Hence,
  
      xyz=1
      =
      ∏_i=0^q+2r+s-1-(2k-ℓ)1/2m-1-2i.
  
  Therefore, for such (x,y,z) ∈,
  
      |er(x,y,z)|
         =
      | ∏_i=0^q+2r+s-11/2m-1-2i - ∏_i=0^q+2r+s-1-(2k-ℓ)1/2m-1-2i|
         ≤∏_i=0^q+2r+s-1-(2k-ℓ)1/2m-1-2i  .
  
  Finally, by (<ref>), we know that 
  
      | (L)_q(M)_r(N)_s - (||)_q(||)_r(||)_s/∏_i=0^q+2r+s-1 2m - 1 - 2i| ≤_(x,y,z) ∈| er(x,y,z) |
      + _(x,y,z) ∈| er(x,y,z) |,
  
  from which the result now follows by using the bounds on |_xx|,|_xy|,|_xz|,|_yy|,|_yz|,|_zz| and on ||, together with (<ref>) and (<ref>)
  
  
  
  
  
   §.§ The probability of simplicity for a random superposition of graphs
  
  
  Before proving Theorem <ref>, it will be useful to show some auxiliary bounds. 
   
  Under the assumptions of Theorem <ref>, we have
  
      ∑_v ∈ [n] d^n(v) = O(n),
  
  
      ∑_v ∈ [n](d^n(v))^2 = O(n),
  
  
      ∑_uv ∈ e(h_n) d^n(u)d^n(v) = O(n),
  
  and
  
      sup_u ∈ [n]∑_v : uv ∈ e(h_n) d^n(v) = o(n),
  
  
  
  
  Equations (<ref>) and (<ref>) follow from the fact that μ_1(p^n) →μ_1(p) < ∞ and μ_2(p^n) →μ_2(p) < ∞. Indeed, we have
  
      ∑_v ∈ [n] d^n(v) 
      = 
      n ∑_k ≥ 1 k p^n(k)
      =
      nμ_1(p^n) = O(n),
  
  and
  
      ∑_v ∈ [n](d^n(v))^2 
      = 
      n ∑_k ≥ 1 k^2 p^n(k)
      =
      nμ_2(p^n) = O(n).
  
  
  Equation (<ref>) follows from the convergence of ∑_i,j ≥ 1 ijα^n(i,j). Notice that, by the definition of α^n,
  
      ∑_uv ∈ e(h_n) d^n(u) d^n(v)
      =
      ∑_i,j ≥ 1( ∑_uv ∈ e(h_n) : d^n(u)=i, d^n(v)=j ij )
      =
      ∑_i,j ≥ 1 ij (nα^n(i,j)).
  
  Hence, 
  
      1/n∑_uv ∈ e(h_n) d^n(u) d^n(v) 
      →∑_i,j ≥ 1 ijα(i,j) < ∞,
  
  implying that 
  
      ∑_uv ∈ e(h_n) d^n(u) d^n(v) = O(n).
  
  
  We will prove the fourth bound by contradiction. To this end, suppose (<ref>) fails. Then we can find c > 0 and a sequence of vertices (u_n, n ≥ 1) with u_n ∈ v(h_n) such that for all n sufficiently large,
  
      ∑_v : u_n v ∈ e(h_n) d^n(v) ≥ cn.
  
  Write (u_n) = _h_n(u_n). List the neighbours of u_n in h_n as N_h_n(u_n) = {v^n_1,… ,v^n_(u_n)} so that d^n(v^n_i) ≥ d^n(v^n_i+1) for all 1 ≤ i < (u_n).
  
  Next, fix D ∈ℕ and let k = k(n) = max{i : d^n(v^n_i) ≥ D}. Then
  
      ∑_i = k+1^(u_n) d^n(v^n_i) ≤ ((u_n)-k)(D-1) = o(n),
  
  the last bound holding since (u_n) = o(n) by assumption. Thus,
  
      ∑_v : u_n v ∈ e(h_n) d^n(v)^2
         =
      ∑_i=1^(u_n) d^n(v^n_i)^2
         ≥∑_i=1^k d^n(v^n_i)^2
         ≥
      D ∑_i=1^k d^n(v^n_i)
         =
      D (∑_v : u_n v ∈ e(h_n) d^n(v) - o(n) )
         ≥
      D(c-o(1))n,
   
  the last bound holding by (<ref>). Since D ∈ℕ was arbitrary, it follows that 
  
      ∑_v ∈ [n] d^n(v)^2
      ≥∑_v : u_nv ∈ e(h_n) d^n(v)^2
      =
      ω(n),
  
  contradicting (<ref>).
  
  
  The next lemma is the last ingredient needed, and also assumes p(0)+p(1)<1, i.e. an asymptotically non-zero proportion of the degrees in G_n are 2 or greater. We will show later that Theorem <ref> is straightforward when p(0)+p(1)=1. 
  
   
  Under the assumptions of Theorem <ref>, suppose additionally that p(0)+p(1)<1. Then
  
      |(G_n)| = Θ(n),
  
  and
  
      |(G_n,h_n)| = Θ(n^2).
  
  
  
  
  Let _n = (G_n), _n = (G_n,h_n), and _n = (G_n,h_n). By their definitions, we have
  
      |_n|
         =
      ∑_v ∈ [n]d^n(v) ( d^n(v) - 1 )/2,  and
      
      |_n|
         =
      ∑_{u < v : uv ∉ e(h_n)}d^n(u) ( d^n(u) - 1 )/2 d^n(v) ( d^n(v) - 1 ).
  
  
  For the upper bounds, by Lemma <ref> we have
  
      |_n|
         =
      ∑_v ∈ [n]d^n(v) ( d^n(v) - 1 )/2≤∑_v ∈ [n] d^n(v)^2
      =
      O(n),  and
      
      |_n|
         =
      ∑_{u < v : uv ∉ e(h_n)}d^n(u) ( d^n(u) - 1 )/2 d^n(v) ( d^n(v) - 1 )
      ≤(∑_v ∈ [n] d^n(v)^2)^2
      = 
      O(n^2).
  
   
  For the lower bounds, first notice that
  
      |_n|
         =
      ∑_v ∈ [n]d^n(v) ( d^n(v) - 1 )/2
         =
      ∑_v ∈ [n] : d^n(v) > 1d^n(v) ( d^n(v) - 1 )/2
         ≥ 
      |{v ∈ [n] : d^n(v) > 1}|
         =
      n(1-p^n(0)-p^n(1))
  
  Since p^n(0)+p^n(1) → p(0)+p(1) < 1 by assumption, this implies |{v ∈ [n] : d^n(v) > 1}| = Θ(n), and so
  
      |_n| ≥ |{v ∈ [n] : d^n(v) > 1}| = Θ(n).
   
  Similarly, we have 
  
      |_n| ≥| { (u,v) : u<v, uv ∉ e(h_n)  and  d^n(u), d^n(v) > 1 }|.
  
  From the conditions of Theorem <ref> we know that max_v ∈ [n]{_h_n(v)} = o(n), which implies that |e(h_n)| = o(n^2). Hence, we have
  
      | { (u,v) : u<v, uv ∉ e(h_n)  and  d^n(u), d^n(v) > 1 }|
      
      =   | { (u,v) : u<v, d^n(u), d^n(v) > 1 }| - o(n^2),
  
  and writing k = k(n) = |{v ∈ [n] : d^n(v) > 1}|, we have 
  
      | { (u,v) : u<v, d^n(u), d^n(v) > 1 }| = k  2 = Θ(k^2) = Θ(n^2),
  
  and hence, |_n| = Θ(n^2). 
  
  
  Let m = m(n) = 1/2∑_v ∈ [n] d^n(v), and let q,r and s be positive integers. Also, in what follows write d^n_max = max_1 ≤ i ≤ n d^n(i); by Fact <ref> we know that d^n_max=o(n^1/2). 
  
  Assume for the time being that p(0)+p(1)<1 and that η > 0. Notice that when η > 0 and μ_1(p) > 0 we have
  
      |_n|/n = 1/n∑_uv ∈ e(h_n) d^n(u)d^n(v) 
      =
      ∑_i,j ≥ 1 ijα^n(i,j)
      →∑_i,j ≥ 1 ijα(i,j)
      =
      μ_1(p) η∈ (0,∞)> 0;
  
  we have μ_1(p) > 0 since p(0) < 1, and μ_1(p) < ∞ since μ_2(p) < ∞. It follows that |_n| = Θ(n).
  
  We first claim that
  
      (L_n)_q (M_n)_r (N_n)_s 
      = 
      (|_n|)_q(|_n|)_r(|_n|)_s/∏_i=0^q+2r+s-1 2m - 1 - 2i (1+o(1)).
  
  From Proposition <ref> we know that
  
      | (L_n)_q (M_n)_r (N_n)_s 
      -
      (|_n|)_q(|_n|)_r(|_n|)_s/∏_i=0^q+2r+s-1 2m - 1 - 2i| ≤ C(S_1+S_2),
  
  where S_1 is defined by the relationship
  
      S_1 ·∏_i=0^q+2r+s-1 (2m - 1 - 2i)
         =
      (|_n|)_q-2(|_n|)_r(|_n|)_s ∑_v ∈ [n] (d^n(v))^3
          +
      (|_n|)_q-1(|_n|)_r-1(|_n|)_s ∑_1 ≤ u ≠ v ≤ n (d^n(u))^3 (d^n(v))^2
          +
      (|_n|)_q-1(|_n|)_r(|_n|)_s-1∑_uv ∈ e(h_n) (d^n(u))^2 d^n(v)
          +
      (|_n|)_q(|_n|)_r-2(|_n|)_s∑_1 ≤ u,v_1,v_2 ≤ n 
       u,v_1,v_2  distinct (d^n(u))^3 (d^n(v_1))^2 (d^n(v_2))^2
          +
      (|_n|)_q(|_n|)_r-1(|_n|)_s-1∑_1 ≤ u, v_1, v_2 ≤ n 
       u,v_1,v_2  distinct
       uv_2 ∈ e(h_n) (d^n(u))^2 (d^n(v_1))^2 d^n(v_2)
          +
      (|_n|)_q(|_n|)_r(|_n|)_s-2∑_uv_1,uv_2 ∈ e(h_n) 
       v_1 ≠ v_2 d^n(u) d^n(v_1) d^n(v_2),
  
  and S_2 is defined by
  
      S_2
         =
      (|_n|)_q(|_n|)_s∑_k=1^r-1 (|_n|)_r-k∑_ℓ = 0^k(d^n_max)^2ℓ∏_i=0^q+2r+s-1-(2k-ℓ)1/2m-1-2i;
  
  recall that we set (k)_ℓ = 0 if ℓ < 0. We now show that
  
      S_1 = o( (|_n|)_q(|_n|)_r(|_n|)_s/∏_i=0^q+2r+s-1 (2m-1-2i))  and 
      S_2 = o( (|_n|)_q(|_n|)_r(|_n|)_s/∏_i=0^q+2r+s-1 (2m-1-2i)).
  
  We will start by bounding S_1. Since |_n|,|_n|,|_n| →∞ as n →∞, to prove the first bound in (<ref>) it suffices to establish the following bounds:
  
      ∑_v ∈ [n] (d^n(v))^3
         = 
      o(|_n|^2),
      ∑_1 ≤ u ≠ v ≤ n (d^n(u))^3 (d^n(v))^2
         =
      o(|_n||_n|),
      ∑_uv ∈ e(h_n) (d^n(u))^2 d^n(v)
         =
      o(|_n||_n|),
      ∑_1 ≤ u, v_1,v_2 ≤ n 
       u,v_1,v_2  distinct (d^n(u))^3 (d^n(v_1))^2 (d^n(v_2))^2
         =
      o(|_n|^2),
      ∑_1 ≤ u, v_1, v_2 ≤ n 
       u,v_1,v_2  distinct
       uv_2 ∈ e(h_n) (d^n(u))^2 (d^n(v_1))^2 d^n(v_2)
         =
      o(|_n||_n|),  and
      ∑_uv_1,uv_2 ∈ e(h_n) 
       v_1 ≠ v_2 d^n(u) d^n(v_1) d^n(v_2)
         =
      o(|_n|^2).
  
  
  Using Lemmas <ref> and <ref>, together with the fact that d^n_max = o(n^1/2), we get the following results:
  
      ∑_v ∈ [n] (d^n(v))^3
      ≤
      d^n_max∑_v ∈ [n] (d^n(v))^2
      =
      o(n^1/2) · O(n)
      =
      o(n^2)
      =
      o(|_n|^2),
  
  
  
      ∑_1 ≤ u ≠ v ≤ n (d^n(u))^3 (d^n(v))^2
         ≤
      d^n_max∑_1 ≤ u ≠ v ≤ n (d^n(u))^2 (d^n(v))^2
         ≤
      d^n_max(∑_v ∈ [n] (d^n(v))^2)^2
      =
      o(n^3)
      =
      o(|_n||_n|),
  
  
  
      ∑_uv ∈ e(h_n) (d^n(u))^2 d^n(v)
      ≤
      d^n_max∑_uv ∈ e(h_n) d^n(u) d^n(v)
      =
      d^n_max |_n|
      =
      o(|_n||_n|),
  
  
  
      ∑_1 ≤ u, v_1,v_2 ≤ n 
       u,v_1,v_2  distinct (d^n(u))^3 (d^n(v_1))^2 (d^n(v_2))^2
         ≤
      d^n_max∑_1 ≤ u, v_1,v_2 ≤ n 
       u,v_1,v_2  distinct (d^n(u))^2 (d^n(v_1))^2 (d^n(v_2))^2
         ≤
      d^n_max(∑_v ∈ [n]^n (d^n(v))^2)^3
      =
      o(n^4)
      =
      o(|_n|^2),
  
  
  
      ∑_1 ≤ u, v_1, v_2 ≤ n 
       u,v_1,v_2  distinct
       uv_2 ∈ e(h_n) (d^n(u))^2 (d^n(v_1))^2 d^n(v_2)
         ≤(d^n_max)^3 ∑_uv ∈ e(h_n) d^n(u)d^n(v)
          =
      o(n^3/2) |_n|
      =
      o(|_n||_n|),
  
  and
  
      ∑_uv_1,uv_2 ∈ e(h_n) 
       v_1 ≠ v_2 d^n(u) d^n(v_1) d^n(v_2)
         =
      ∑_uv ∈ e(h_n) d^n(u)d^n(v) ·∑_w : uw ∈ e(h_n) d^n(w)
         ≤∑_uv ∈ e(h_n) d^n(u)d^n(v) ·( sup_u ∈ [n]∑_w : uw ∈ e(h_n) d^n(w) )
         =
      |_n| · o(n)
         =
      o(|_n|^2),
  
  the last bound holding as _n = Θ(n).
  
  To prove the bound on S_2 from (<ref>), first notice that 
  
      S_2 
         =
      (|_n|)_q(|_n|)_s∑_k=1^r-1 (|_n|)_r-k∑_ℓ = 0^k (d^n_max)^2ℓ∏_i=0^q+2r+s-1-(2k-ℓ)1/2m-1-2i
         =
      (|_n|)_q(|_n|)_s/∏_i=0^q+s-1 2m-1-2i∑_k=1^r-1 (|_n|)_r-k∑_ℓ = 0^k (d^n_max)^2ℓ∏_i=q+s^q+2r+s-1-(2k-ℓ)1/2m-1-2i.
  
  Hence, it suffices to show the following:
  
      ∑_k=1^r-1 (|_n|)_r-k∑_ℓ = 0^k (d^n_max)^2ℓ∏_i=q+s^q+2r+s-1-(2k-ℓ)1/2m-1-2i   =
      o ( (|_n|)_r/∏_i=q+s^q+2r+s-1 2m-1-2i).
  
  Since r is fixed, we need only show that for arbitrary k ∈ [1,r-1] and ℓ∈ [0,k],
  
      (|_n|)_r-k (d^n_max)^2ℓ∏_i=q+s^q+2r+s-1-(2k-ℓ)1/2m-1-2i   =
      o ( (||)_r/∏_i=q+s^q+2r+s-1 2m-1-2i).
  
  By cancelling out some terms, this follows if we can show that
  
      (d^n_max)^2ℓ   =
      o ( (|_n|-(r-k))_k/∏_i=q+2r+s-(2k-ℓ)^q+2r+s-1 2m-1-2i).
  
  Now since m = Θ(n), |_n| = Θ(n^2), and r is a constant, this in turn holds, provided that 
  
      (d^n_max)^2ℓ   =
      o ( n^2k/n^2k-ℓ)
         =
      o ( n^ℓ),
  
  which holds since d^n_max = o(n^1/2).
  
  Therefore, 
  
      S_1 + S_2 = o( (|_n|)_q(|_n|)_r(|_n|)_s/∏_i=0^q+2r+s-1 2m - 1 - 2i),
  
  which proves that
  
      (L_n)_q (M_n)_r (N_n)_s 
      = 
      (|_n|)_q(|_n|)_r(|_n|)_s/∏_i=0^q+2r+s-1 2m - 1 - 2i (1+o(1)).
  
  Furthermore, since q,r and s are fixed, we obtain that 
  
      (|_n|)_q(|_n|)_r(|_n|)_s/∏_i=0^q+2r+s-1 2m - 1 - 2i
      
      =     |_n|^q |_n|^r |_n|^s/(2m)^q+2r+s(1+o(1))
      
      =     (|_n|/∑_v ∈ [n] d^n(v))^q (|_n|/(∑_v ∈ [n] d^n(v))^2)^r(|_n|/∑_v ∈ [n] d^n(v))^s(1+o(1))
  
  
  Next, we claim that
  
      |_n|/∑_v ∈ [n] d^n(v)   →ν/2,
      |_n|/(∑_v ∈ [n] d^n(v))^2→ν^2/4,  and |_n|/∑_v ∈ [n] d^n(v)→η.
  
  For the first of these three claims, we have
  
      |_n|/∑_v ∈ [n] d^n(v) 
      =
      1/2∑_v ∈ [n] d^n(v)(d^n(v)-1)/∑_v ∈ [n] d^n(v)   =
      1/2∑_v ∈ [n] (d^n(v))^2 - ∑_v ∈ [n] d^n(v)/∑_v ∈ [n] d^n(v)
         =
      1/2( μ_2(p^n) - μ_1(p^n)/μ_1(p^n))
      →ν/2.
  
  For the second, we have
  
      |_n|/(∑_v ∈ [n] d^n(v))^2
      
      =     1/2∑_{u < v : uv ∉ e(h_n)} d^n(u) ( d^n(u) - 1 ) d^n(v) ( d^n(v) - 1 )/(∑_v ∈ [n] d^n(v))^2
      
      =     1/4 (∑_v ∈ [n] d^n(v))^2( [∑_v ∈ [n] d^n(v) ( d^n(v) - 1 )]^2 - ∑_v ∈ [n][d^n(v) ( d^n(v) - 1 ) ]^2
                                              - ∑_uv ∈ e(h_n) d^n(u) ( d^n(u) - 1 ) d^n(v) ( d^n(v) - 1 ) ).
  
  The second and third terms vanish in the limit since μ_1(p) > 0 and so
  
      (∑_v ∈ [n] d^n(v))^2 = Ω(n^2),
  
  and
  
      ∑_v ∈ [n][d^n(v) ( d^n(v) - 1 ) ]^2
         ≤
      (d^n_max)^2 ∑_v ∈ [n] (d^n(v))^2
      =
      (d^n_max)^2 nμ_2(p^n)
      =
      o(n^2),
  
  and
  
      ∑_uv ∈ e(h_n) d^n(u) ( d^n(u) - 1 ) d^n(v) ( d^n(v) - 1 )
         ≤
      (d^n_max)^2 ∑_uv ∈ e(h_n) d^n(u) d^n(v)
         =
      (d^n_max)^2 |_n|
         =
      o(n^2).
  
  Therefore,
  
      |_n|/(∑_v ∈ [n] d^n(v))^2   =
      1/4[∑_v ∈ [n] d^n(v) ( d^n(v) - 1 )]^2/(∑_v ∈ [n] d^n(v))^2 (1+o(1))
         →1/4(μ_2(p) - μ_1(p))^2/(μ_1(p))^2
         =
      ν^2/4.
  
  For the third claim, we have
  
      |_n|/∑_v ∈ [n] d^n(v)
      =
      ∑_uv ∈ e(h_n) d^n(u)d^n(v)/∑_v ∈ [n] d^n(v)   =
      ∑_i,j ≥ 1 ijα^n(i,j)/μ_1(p^n)
         →∑_i,j ≥ 1 ijα(i,j)/μ_1(p)
      =
      η.
  
  
  Therefore,
  
      lim_n →∞(L_n)_q (M_n)_r (N_n)_s
      
      =    lim_n →∞(|_n|)_q(|_n|)_r(|_n|)_s/∏_i=0^q+2r+s-1 2m - 1 - 2i (1+o(1)) 
      
      =    lim_n →∞(|_n|/∑_v ∈ [n] d^n(v))^q (|_n|/(∑_v ∈ [n] d^n(v))^2)^r(|_n|/∑_v ∈ [n] d^n(v))^s (1+o(1))
      
      =    ( ν/2 )^q ( ν^2/4 )^r ( η)^s.
  
  It then follows, by Theorem 2.6 of <cit.>, that the random variables L_n,M_n and N_n converge to independent Poisson random variables with parameters ν/2,ν^2/4 and η respectively. This proves the theorem in the case that p(0)+p(1)<1 and η > 0.
  
  Lastly we will deal with the cases that arise if p(0)+p(1) = 1 or if η = 0. First, if η = 0 then lim_n →∞∑_i,j ≥ 1 ij α^n(i,j) = ∑_i,j ≥ 1 ij α(i,j) = 0. For any two half-edges ui and vj with u,v ∈ [n], i ∈ [d^n(u)] and j ∈ [d^n(v)], we have ui,vj=1 = 1/2m-1 from the definition of the configuration model. So by (<ref>), since m = m(n) = nμ_1(p^n)/2 = Θ(n), we have that 
  
      N_n 
      =
      ∑_uv ∈ e(h_n)∑_i ∈ [d^n(u)]∑_j ∈ [d^n(v)]ui,vj=1   =
      ∑_uv ∈ e(h_n) d^n(u)d^n(v)/2m-1
         =
      n/2m-1∑_i,j ≥ 1 ij α^n(i,j)
      =
      o(1).
  
  Hence, lim_n →∞N_n = 0. In this case, if p(0)+p(1)<1 then a reprise of the argument leading to (<ref>) gives that for all q,r ≥ 1,
  
      lim_n →∞(L_n)_q (M_n)_r = (ν/2)^q(ν^2/4)^r,
  
  and therefore that L_n and M_n converge to independent Poisson random variables with parameters ν/2 and ν^2/4 respectively.
  
  Lastly, we deal with the case when p(0)+p(1)=1. In this case, μ_2(p) = μ_1(p), so ν = 0. Furthermore, 
  
      L_n
      = 
      1/2∑_v ∈ [n] d^n(v)(d^n(v)-1)/2m-1
      =
      n/4m-2(μ_2(p^n) - μ_1(p^n)).
  
  Since μ_2(p^n) - μ_1(p^n) →μ_2(p) - μ_1(p) = 0, we get that lim_n →∞L_n = 0, and an analogous argument shows that lim_n →∞M_n = 0. In this case, another reprise of the argument leading to (<ref>) gives that for all s ≥ 1,
  
      lim_n →∞(N_n)_s = η^s,
  
  so N_n is asymptotically Poisson(η) distributed. 
  
  
  
  First, the fact that ∑_k,ℓ≥ 0 kℓ·α(k,ℓ) < ∞ appears in (<ref>), above,  from which it is immediate that η < ∞. 
  Next, let G_-(^n) be the subgraph of G(^n) with edge set (G(^n))∖(T(^n)), and let ^n_- be the degree sequence of G_-(^n),  as defined in Section <ref> previous to Proposition <ref>. 
  Finally, write L_n=L(G_-(^n)), M_n=M(G_-(^n),T(^n)), and N_n=N(G_-(^n),T(^n)).  Our aim is to apply Theorem <ref>,  with h_n=T(^n) and G_n=G_-(^n)=G(^n)-T(^n). Note that with these choices, we have α^n(k,l) = n^-1A^n(k,l), where A^n(k,l) is as in Proposition <ref>.
  Moreover, we have 
  
      ∑_l ≥ 0 A^n(k,l)
      = #{u ∈ [n]: d^n_-(u)=k}  .
  
  
  Conditionally given T(^n), the graph G_-(^n) is a random graph with degree sequence ^n_-. By Proposition <ref> we know that α^n(k,l) α(k,l) for all k,l ≥ 0, and that 
  
      ∑_k,l ≥ 0 klα^n(k,l) ∑_k,l ≥ 0 klα(k,l).
  
  Moreover, since α defines a probability distribution, it must be that for all k we have
  
      p^n_-(k) := 1/n#{u ∈ [n]: d^n_-(u)=k}
      = 1/n∑_l≥ 0 A^n(k,l) = ∑_l≥ 0α^n(k,l) ∑_l ≥ 0α(k,l)  .
  
  Setting p_-(k) = ∑_l ≥ 0α(k,l), then (<ref>) states that p^n_-(k)  p_-(k) for all k ≥ 0. Moreover, since p^n_-(k) ≤ p^n(k), p^n_-(k)  p_-(k), and p^n(k)  p(k) for all k ≥ 0, it follows that μ_2(p_-) ≤μ_2(p) < ∞ and μ_2(p^n_-) μ_2(p_-).
  From these observations, Fact <ref> then implies that 
  
      max_v ∈ [n]deg_T(^n)(v)≤max_v ∈ [n]deg_G_n(v) = o(n^1/2)  .
  
  Since μ_2(p^n_-)μ_2(p_-), we also have μ_1(p^n_-) μ_1(p_-); but 
  
      nμ_1(p^n_-) = ∑_i=1^n d^n_-(u) = (∑_i=1^n d^n(u)) - 2(n-1)  ,
  
  so μ_1(p_-)=μ_1(p)-2. Thus, if μ_1(p)>2 then μ_1(p_-)>0, so p_-(0)<1. In this case, applying Theorem <ref>, it follows that conditionally given T(^n), 
  
      Dist(L_n,M_n,N_n) - Poi(ν/2)⊗Poi(ν^2/4)⊗Poi(η)_TV 0
  
  as n →∞. 
  If (L,M,N) is Poi(ν/2)⊗Poi(ν^2/4)⊗Poi(η)-distributed, then we have L=M=N=0=exp(-ν/2- ν^2/4-η); 
  since 
  G(^n) is simple if and only if L_n=M_n=N_n=0, it follows that 
  
      G(^n) simpleT(^n)    = L_n=M_n=N_n=0T(^n)
         L=M=N=0= exp(-ν/2-ν^2/4-η)  ,
   
  as required. 
  
  It remains to treat the case that μ_1(p)=2, which implies that μ_1(p_-)=0 and p_-(0)=1. This case requires a separate argument, which is more involved than one might expect. We note immediately that in this situation, m=(1+o(1))n as n →∞. 
  
  Write G_n' for the graph obtained from G_-(^n) by removing the edge Γ(^n). Then let L_n'=L(G_n'), M_n'=M(G_n',T(^n)), and N_n'=N(G_n',T(^n)). Then G_n' is simple precisely if L_n'+M_n'+N_n'=0. We will first prove that L_n' + M_n' + N_n' 0, then explain how to deal with the root edge.
  
  By Proposition <ref>, we know that the non-root half-edges chosen for T(^n) form a uniformly random subset 𝒮^n of ⋃_i=1^n {i1, … , i(d^n(i)-1)} of size n-1. The half-edges which are paired to form G_-(^n) are precisely the edges of 
  𝒰:= ⋃_i=1^n {i1, … , i(d^n(i)-1)}∖𝒮^n, together with the unique unpaired root half-edge of T(^n). 
  
  Write 𝒰 for the set of half-edges paired to form G_n'. By the observations of the preceding paragraph, 𝒰 is a uniformly random subset of ⋃_i=1^n {i1, … , i(d^n(i)-1)} of size 2(m-n). Moreover, conditionally given 𝒰, the pairing of half-edges in 𝒮 is uniformly random and independent of T(^n). Therefore, we can construct (G(^n),T(^n),Λ(^n)) as follows. First sample a sequence of m-n disjoint pairs of half-edges from ⋃_i=1^n {i1, … , i(d^n(i)-1)} uniformly at random and join them to form edges; this determines the set 𝒰, and all edges of G_n'. Next, build T(^n) via Pitman's additive coalescent applied to ⋃_i=1^n {i1, … , i(d^n(i)-1)}∖𝒰. Finally, pair the root half-edge of T^n with the sole remaining unpaired non-root half-edge. We analyze this construction procedure in order to bound the expected number of loops and multiple edges in G_n'.
  
  Let (h_1,h_2) be a half-edge pair chosen for G_n' in the construction procedure just above. Then h_1 and h_2 are uniform random half-edges chosen from ⋃_i=1^n {i1,…,i(d^n(i)-1)}, and (h_1,h_2) is a loop if v(h_1) = v(h_2). Hence,
  
      L_n   =
      | e(G_n') | v(h_1) = v(h_2)
         =
      (m-n) ∑_i=1^n v(h_1) = v(h_2) = i
         =
      (m-n) ∑_i=1^n (d^n(i)-1)(d^n(i)-2)/(2m-(n-1))(2m-n).
  
  Similarly, edges (h_1,h_2) and (h_3,h_4) form a double edge if v(h_1) = v(h_3) and v(h_2) = v(h_4) or if v(h_1) = v(h_4) and v(h_2) = v(h_3). Hence,
  
      M_n
      
      =     (| e(G_n') |) (| e(G_n')) | - 1 ) ∑_1 ≤ i < j ≤ n4(d^n(i)-1)(d^n(i)-2)(d^n(j)-1)(d^n(j)-2)/(2m-n+1))(2m-n)(2m-n-1)(2m-n-2)
      
      =     
      (m-n) (m-n-1) ∑_1 ≤ i < j ≤ n4(d^n(i)-1)(d^n(i)-2)(d^n(j)-1)(d^n(j)-2)/(2m-n+1)(2m-n)(2m-n-1)(2m-n-2)
      ≤    
      2( (m-n) ∑_i=1^n (d^n(i)-1)(d^n(i)-2)/(2m-n-1)(2m-n-2))^2.
   
  Since m=n+o(n), we have m-n-1/2m-n-2 = o(1). Since also ∑_i=1^n (d^n(i)-1)(d^n(i)-2) ≤∑_i=1^n d^n(i)^2 = O(n) = O(2m-n-1), it follows from the two preceding displayed inequalities that L_n' + M_n' 0.
  
  To show that N_n' 0, we will again use Proposition <ref>. Given a set ⊆⋃_i=1^n {i1,…,i(d^n(i)-1)}, write _i = ∩{i1, … , i(d^n(i)-1)}. By (<ref>) we know that for any set  as above with || = n-1, for all 1 ≤ i ≤ n-1, for any h ∈ and any root half-edge r with v(r) ≠ v(h), 
  
      (r_i,s_i) = (r,h)𝒮^n =  = (r_1,s_1) = (r,h)𝒮^n = .
  
  Moreover, by construction, T(d^n) and G_n' are conditionally independent given 𝒮^n, so for any 1 ≤ i≤ n-1, 
  
      m_G_n'(v(r_i)v(s_i))𝒮^n = 
      
      =     m_G_n'(v(r_1)v(s_1))𝒮^n = 
      
      =     ∑_j=1^n ∑_k=1 
       k ≠ j^n v(r_1) = j, v(s_1) = k𝒮^n = ·m_G_n'(jk)𝒮^n = 
      .
  
  Now, by Proposition <ref>, 
  
      v(r_1) = j, v(s_1) = k𝒮^n =  = 
      | _k |/(n-1)^2.
  
  Also, 
  
      m_G_n'(jk)𝒮^n =    =
      (m-n) ·(d^n(j)-1-|_j|)(d^n(k)-1-|_k|)/(2m-2(n-1))(2m-2(n-1)-1).
   
  The term m-n above accounts for the number of edges of G_n'; the fraction is the probability that a uniformly random pair of half-edges from (⋃_l=1^n {l1,…,l(d^n(i)-1)}) ∖ are incident to vertices j and k. Combining these formulas, we then have that for all 1 ≤ i ≤ n-1, 
  
      m_G_n'(v(r_i)v(s_i))𝒮^n = 
      ≤    ∑_j=1^n ∑_k=1 
       k ≠ j^n | _k |/(n-1)^2· (m-n) ·(d^n(j)-1-|_j|)(d^n(k)-1-|_k|)/(2m-2(n-1))(2m-2(n-1)-1)
      
      =      O(1)·∑_k=1^n | _k |/(n-1)^2·(d^n(k)-1-|_k|)/(2(m-n)+1)∑_j=1 
       j ≠ k^n (d^n(j)-1-|_j|).
  
  Now, since ∑_j=1^n |_j| = ||=n-1, we have 
  
      ∑_j=1 
       j ≠ k^n (d^n(j)-1-|_j|)
         =
      2m - n - || - ( d^n(k) - 1 - | _k | )
      ≤
      2(m-n)-1  ,
  
  and it follows that 
  
      m_G_n'(v(r_i)v(s_i))𝒮^n = 
      =O(1)·∑_k=1^n | _k | (d^n(k)-1-|_k|)/2(n-1)^2.
  
  Taking expectation over 𝒮^n in this bound, it follows that 
  
      m_G_n'(v(r_i)v(s_i))≤1/(n-1)^2∑_k=1^n | _k | (d^n(k)-1-|_k|).
  
  We now show that ∑_k=1^n | _k | (d^n(k)-1-|_k|) = o(n). Notice that | _k | ≤ d^n(k) and that d^n(k)-1-|_k| = d^n_-(k), unless k is incident to the unpaired root half-edge, in which case d^n(k)-1-|_k| = d^n_-(k) - 1 ≥ 0. Letting r be the unpaired root half-edge, it then follows that
  
      ∑_k=1^n | _k | (d^n(k)-1-|_k|) 
      ≤∑_k=1^n (d^n(k))^2 d^n_-(k) > 0.
  
  Since |{k: d^n_-(k)>0}| ≤ m-n = o(n), by the second assertion of Fact <ref> it follows that ∑_k=1^n d^n(k)^2d^n_-(k) >0 = o(n), which combined with the two preceding inequalities yields that 
  
      m_G_n'(v(r_i)v(s_i)) = o( 1/n).
  
  Summing over i, it follows that 
  
      N_n' = ∑_i=1^n m_G_n'(v(r_i)v(s_i)) = o(1).
  
  At this point we know that L_n'+M_n'+N_n'→ 0. We now how to deduce the same for L_n+M_n+N_n. We provide full details only in the case that m-n →∞, i.e., that the number of edges of G_-(^n) tends to infinity, and briefly explain the argument in the simpler case that m-n=O(1).
  
  By Proposition <ref>, for any pair (g,t) where g is a graph with degree sequence ^n and t is a spanning tree of g, we have 
  
      (G(^n),T(^n))=(g,t)∝∑_γ∈ e(g-t)2^γ is a loop· m_g-t(γ)/∏_i=1^n 2^m_g-t(ii)·∏_e ∈(g) m_g-t(e)!  ,
  
  and for any edge γ of g-t, 
  
      Γ(^n)=γ(G(^n),T(^n))=(g,t)∝ 2^γ is a loop· m_g-t(γ).
  
  If the graph with edge set e(g)-(e(t) ∪γ) is simple, then g-t has at most one loop, and no edge with multiplicity more than two, so 
  
      sup_e ∈ e(g-t)Γ(^n)=e(G(^n),T(^n))=(g,t)≤2/|e(g-t)|.
  
  In particular, writing 
  
      ℬ(g,t) = (g)∪(g,t) ∪⋃_((ui_i,vj_1),(ui_2,vj_2))∈(g,t){(ui_i,vj_1),(ui_2,vj_2)}  ,
  
  and recalling that the half-edges comprising Γ(^n) are Γ^-(^n) and Γ^+(^n), 
  it follows that 
  
      (Γ^-(^n),Γ^+(^n)) ∈ℬ(G_-(^n),T(^n))(G(^n),T(^n))
         ≤2|ℬ(G_-(^n),T(^n))|/|e(G_-(^n))|G_n' simple + G_n' not simple
         ≤4(L(G_-(^n))+N(G_-(^n),T(^n))+M(G_-(^n),T(^n)))/|e(G_-(^n))|G_n' simple+G_n' not simple
          = 4(L_n+M_n+N_n)/m-(n-1)+G_n' not simple  ;
  
  the last inequality is not tight unless M(G_-(^n),T(^n))=0. Now, 
  
      L_n+M_n+N_n  ≤ 3(L_n'+M_n'+N_n'+ (Γ^-(^n),Γ^+(^n)) ∈ℬ(G_-(^n),T(^n)))  ;
  
  this inequality is never tight but it suffices for our purposes. 
  Using this bound, and taking expectations in the previous conditional probability bound, we obtain that 
  
      (Γ^-(^n),Γ^+(^n)) ∈ℬ(G_-(^n),T(^n))
         ≤12/m-(n-1)L_n'+M_n'+N_n'+1 + G_n' not simple 
          = 12/m-(n-1)L_n'+M_n'+N_n'+1 + L_n'+M_n'+N_n' > 0  .
  
  Since L_n'+M_n'+N_n'→ 0, if m-(n-1) →∞ it follows that 
  
      (Γ^-(^n),Γ^+(^n)) ∈ℬ(G_-(^n),T(^n)) 0
  
  in which case (<ref>) and the fact that L_n'+M_n'+N_n'  0 together imply that L_n+M_n+N_n  0 as required. 
  
  Finally, if m-n=O(1), the fact that L_n+M_n+N_n  0 can be seen as follows. Let h be a uniformly random half-edge from ⋃_1 ≤ i ≤ n{i1,…,i(d^n(i)-1)}. 
  Then with high probability, d^n(v(h))=O(1). Since ||=|⋃_1 ≤ i ≤ n{i1,…,i(d^n(i)-1)}∖𝒮^n|=2(m-n)=O(1), it follows that with high probability d^n(v(h))=O(1) for all edges of ⋃_1 ≤ i ≤ n{i1,…,i(d^n(i)-1)}∖ℋ and that v(h) v(h') for all distinct h,h' ∈. This already implies that L_n+M_n=0 with probability 1-o(1). 
  Finally, by considering Pitman's additive coalescent it is not hard to see that for any vertex v with d^n(v)=O(1), the probability that v is the root of T^n(v) or is adjacent to the root is o(1), and that for any two vertices v,w with d^n(v)=O(1) and d^n(w)=O(1), the probability that v and w are adjacent is o(1). (Verifying the assertions of the last sentence in detail is left to the reader.) This immediately implies that N_n=0 with probability 1-o(1) and so completes the proof. 
  
  
  
  
  § ACKNOWLEDGEMENTS
   
  Both authors thank Serte Donderwinkel and an anonymous referee for a very careful reading of the paper and for several useful comments.
  
  
  
  20
  
  
  urlstyle
  
  [Abraham et al.(2013)Abraham, Delmas, and Hoscheit]MR3035742
  Romain Abraham, Jean-François Delmas, and Patrick Hoscheit.
  A note on the Gromov-Hausdorff-Prokhorov distance between
    (locally) compact metric measure spaces.
  Electron. J. Probab., 18:0 no. 14, 21, 2013.
  10.1214/EJP.v18-2116.
  URL <https://arxiv.org/abs/1202.5464>.
  
  [Berestycki et al.(2017)Berestycki, Laslier, and Ray]MR3681382
  Nathanaël Berestycki, Benoît Laslier, and Gourab Ray.
  Critical exponents on Fortuin-Kasteleyn weighted planar maps.
  Comm. Math. Phys., 3550 (2):0 427–462, 2017.
  ISSN 0010-3616.
  10.1007/s00220-017-2933-7.
  
  [Bernardi(2007)]MR2285813
  Olivier Bernardi.
  Bijective counting of tree-rooted maps and shuffles of parenthesis
    systems.
  Electron. J. Combin., 140 (1):0 Research Paper
    9, 36, 2007.
  URL
    <http://www.combinatorics.org/Volume_14/Abstracts/v14i1r9.html>.
  
  [Bernardi(2008)]MR2438581
  Olivier Bernardi.
  Tutte polynomial, subgraphs, orientations and sandpile model: new
    connections via embeddings.
  Electron. J. Combin., 150 (1):0 Research Paper
    109, 53, 2008.
  URL
    <http://www.combinatorics.org/Volume_15/Abstracts/v15i1r109.html>.
  
  [Bousquet-Mélou and Courtiel(2015)]MR3366469
  Mireille Bousquet-Mélou and Julien Courtiel.
  Spanning forests in regular planar maps.
  J. Combin. Theory Ser. A, 135:0 1–59, 2015.
  ISSN 0097-3165.
  10.1016/j.jcta.2015.04.002.
  URL <https://arxiv.org/abs/1306.4536>.
  
  [Broutin and Marckert(2014)]MR3188597
  Nicolas Broutin and Jean-François Marckert.
  Asymptotics of trees with a prescribed degree sequence and
    applications.
  Random Structures Algorithms, 440 (3):0
    290–316, 2014.
  ISSN 1042-9832.
  10.1002/rsa.20463.
  URL <https://arxiv.org/abs/1110.5203>.
  
  [Ewain Gwynne and Sheffield(2017)]gwynne2017
  Jason Miller Ewain Gwynne and Scott Sheffield.
  The Tutte embedding of the mated-CRT map converges to Liouville
    quantum gravity.
  arXiv:1705.11161 [math.PR], May 2017.
  URL <https://arxiv.org/abs/1705.11161>.
  
  [Greenhill et al.(2014)Greenhill, Kwan, and Wind]MR3177540
  Catherine Greenhill, Matthew Kwan, and David Wind.
  On the number of spanning trees in random regular graphs.
  Electron. J. Combin., 210 (1):0 Paper 1.45,
    26, 2014.
  10.37236/3752.
  URL
    <https://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i1p45>.
  
  [Greenhill et al.(2017)Greenhill, Isaev, Kwan, and McKay]MR3645782
  Catherine Greenhill, Mikhail Isaev, Matthew Kwan, and Brendan D. McKay.
  The average number of spanning trees in sparse graphs with given
    degrees.
  European J. Combin., 63:0 6–25, 2017.
  ISSN 0195-6698.
  10.1016/j.ejc.2017.02.003.
  URL <https://arxiv.org/abs/1606.01586>.
  
  [Gwynne et al.(2018)Gwynne, Kassel, Miller, and Wilson]MR3778352
  Ewain Gwynne, Adrien Kassel, Jason Miller, and David B. Wilson.
  Active spanning trees with bending energy on planar maps and
    SLE-decorated Liouville quantum gravity for κ > 8.
  Comm. Math. Phys., 3580 (3):0 1065–1115,
    2018.
  ISSN 0010-3616.
  10.1007/s00220-018-3104-1.
  URL <https://arxiv.org/abs/1603.09722>.
  
  [Gwynne et al.(2020)Gwynne, Holden, and Sun]MR4126936
  Ewain Gwynne, Nina Holden, and Xin Sun.
  A mating-of-trees approach for graph distances in random planar maps.
  Probab. Theory Related Fields, 1770 (3-4):0
    1043–1102, 2020.
  ISSN 0178-8051.
  10.1007/s00440-020-00969-8.
  URL <https://arxiv.org/abs/1711.00723>.
  
  [Holden and Sun(2018)]MR3861296
  Nina Holden and Xin Sun.
  SLE as a mating of trees in Euclidean geometry.
  Comm. Math. Phys., 3640 (1):0 171–201, 2018.
  ISSN 0010-3616.
  10.1007/s00220-018-3149-1.
  URL <https://arxiv.org/abs/1610.05272>.
  
  [Li et al.(2017)Li, Sun, and Watson]li2017
  Yiting Li, Xin Sun, and Samuel S. Watson.
  Schnyder woods, SLE(16), and Liouville quantum gravity.
  arXiv:1705.03573, May 2017.
  URL <https://arxiv.org/abs/1705.03573>.
  
  [McKay(1981)]MR657198
  Brendan D. McKay.
  Spanning trees in random regular graphs.
  In Proceedings of the Third Caribbean Conference on
    Combinatorics and Computing (Bridgetown, 1981), pages 139–143. Univ.
    West Indies, Cave Hill Campus, Barbados, 1981.
  
  [Miller and Sheffield(2019)]MR4010949
  Jason Miller and Scott Sheffield.
  Liouville quantum gravity spheres as matings of finite-diameter
    trees.
  Ann. Inst. Henri Poincaré Probab. Stat., 550
    (3):0 1712–1750, 2019.
  ISSN 0246-0203.
  10.1214/18-aihp932.
  URL <https://arxiv.org/abs/1506.03804>.
  
  [Moon(1970)]MR0274333
  J. W. Moon.
  Counting labelled trees, volume 1969 of From lectures
    delivered to the Twelfth Biennial Seminar of the Canadian Mathematical
    Congress (Vancouver.
  Canadian Mathematical Congress, Montreal, Que., 1970.
  
  [Mullin(1967)]MR205882
  R. C. Mullin.
  On the enumeration of tree-rooted maps.
  Canadian J. Math., 19:0 174–183, 1967.
  ISSN 0008-414X.
  10.4153/CJM-1967-010-x.
  URL <https://doi.org/10.4153/CJM-1967-010-x>.
  
  [Pitman(1999)]MR1673928
  Jim Pitman.
  Coalescent random forests.
  J. Combin. Theory Ser. A, 850 (2):0 165–193,
    1999.
  ISSN 0097-3165.
  10.1006/jcta.1998.2919.
  URL <https://www.stat.berkeley.edu/ pitman/457.pdf>.
  
  [van der Hofstad(2017)]MR3617364
  Remco van der Hofstad.
  Random graphs and complex networks. Vol. 1.
  Cambridge Series in Statistical and Probabilistic Mathematics, [43].
    Cambridge University Press, Cambridge, 2017.
  ISBN 978-1-107-17287-6.
  10.1017/9781316779422.
  URL <https://www.win.tue.nl/ rhofstad/NotesRGCN.pdf>.
  
  [Walsh and Lehman(1972)]MR314687
  T. Walsh and A. B. Lehman.
  Counting rooted maps by genus. II.
  J. Combinatorial Theory Ser. B, 13:0 122–141, 1972.
  ISSN 0095-8956.
  10.1016/0095-8956(72)90049-4.
  URL
    <https://www.sciencedirect.com/science/article/pii/0095895672900494>.
  
  
                   
  
  