The diameter of the minimum spanning tree of the complete graph with
inhomogeneous random weights

Othmane SAFSAFI

We study a new type of random minimum spanning trees. It is built on the
complete graph where each vertex is given a weight, which is a positive real
number. Then, each edge is given a capacity which is a random variable that
only depends on the product of the weights of its endpoints. We then study the
minimum spanning tree corresponding to the edge capacities. Under a condition
of finite moments on the node weights, we show that the expected diameter and
typical distances of this minimum spanning tree are of order $n^{1/3}$. This
is a generalization of the results of Addario-Berry, Broutin, and Reed (2009).
We then use our result to answer a conjecture in statistical physics about
typical distances on a closely related object. This work also sets the ground
for proving the existence of a non-trivial scaling limit of this spanning tree
(a generalization of the result in Addario-Berry, Broutin, Goldschmidt, and
Miermont (2017)). Our proof is based on a detailed study of rank-1 critical
inhomogeneous random graphs, done in Safsafi (2020), and novel couplings
between exploration trees related to those graphs and Galton-Watson trees.
Figure 1: An example of the random trees we study in this article. We
highlighted a typical random path in the tree in red.

##  1 Introduction

###  1.1 The model

Let $G=(V,E)$ be a connected graph with $n$ nodes and $m$ edges. Let
$e_{1},e_{2},...,e_{m}$ be positive real numbers that represent capacities on
the edges of $G$. Assume that these capacities are all distinct, then there
exists a unique spanning tree $T=(V,E_{T})$ that minimizes the sum of the
capacities on the edges:

$\sum_{e_{i}\in E_{T}}e_{i}.$

We call this tree the minimum spanning tree (MST). If the graph is not
connected the set of minimum spanning trees of its connected components is
called the minimum spanning forest. If the weights are independent random
variables with atomless distributions, the MST will be almost surely unique.
The minimum spanning tree is an important object in combinatorial
optimization, it can be easily computed (see Kruskal (1956) and Prim (1957)),
and it can be used to construct approximations to more difficult problems such
as the traveling salesman (Vazirani (2001)). The study of random minimum
spanning trees is also of independent interest in statistical physics (Chen,
López, Havlin, and Stanley (2006), Wu, Braunstein, Havlin, and Stanley (2006),
Braunstein, Wu, Chen, Buldyrev, Kalisky, Sreenivasan, Cohen, Lopez, Havlin,
and Stanley (2007)).

From a probabilistic perspective, the minimum spanning tree has been studied
extensively and on various graphs and models of randomness. Let
$\mathcal{T}_{n}$ denote the minimum spanning tree of a complete graph of size
$n$ with i.i.d. $[0,1]$-uniform random capacities on its edges. Frieze (1985)
proved that the total capacity of $\mathcal{T}_{n}$ converges to
$\zeta(3)=\sum_{k=1}^{+\infty}\frac{1}{k^{3}}$. Aldous (1990) found the limit
distribution of the degree of node $1$ in $\mathcal{T}_{n}$. These results are
based on a local study of the minimum spanning tree.

Another type of questions concerns global properties of the random MST. For
instance, Addario-Berry, Broutin, and Reed (2009) showed that the diameter
(maximum number of edges of a shortest path between two nodes) of
$\mathcal{T}_{n}$ is of order $n^{1/3}$. This estimate was used crucially by
Addario-Berry, Broutin, Goldschmidt, and Miermont (2017) to show that there
exists a measured metric space which is a scaling limit of $\mathcal{T}_{n}$
with distances scaled by $n^{-1/3}$. In this paper, we extend the results of
Addario-Berry et al. (2009) to a more general class of random minimum spanning
trees. Let $n\in\mathbb{N}$ and $\textbf{W}=(w_{1},w_{2},..w_{n})$, with
$0<w_{n}\leq w_{n-1}\leq...\leq w_{1}$, be a vector of positive weights, and
consider the complete graph of size $n$. W will always depend implicitly on
$n$. To each non-oriented edge $\\{i,j\\}$, $i\neq j$, we associate the random
capacity $E_{\\{i,j\\}}$, which is an exponential random variable of rate
$w_{i}w_{j}$. The capacities are then used to create a sequence of graphs. For
each $p\in[0,+\infty]$ let $G(\textbf{W},p)$ be the graph on $\\{1,2....,n\\}$
containing the edges of capacity at most $p$, so the edge set of
$G(\textbf{W},p)$ is:

$\left\\{\\{i,j\\}|E_{\\{i,j\\}}\leq p\right\\}.$

Then $(G(\textbf{W},p))_{p\in[0,+\infty]}$ is an increasing sequence of graphs
(for inclusion), and for each fixed value of $p$, $G(\textbf{W},p)$ is called
a rank-1 inhomogeneous random graph. Now for each $p$, consider the forest
$\mathcal{T}(\textbf{W},p)$ constructed by deleting edges from
$G(\textbf{W},p)$ as follows:

We construct a sequence of graphs
$(\mathcal{G}(\textbf{W},p,i))_{\binom{n}{2}\geq i\geq 1}$ such that
$\mathcal{G}(\textbf{W},p,\binom{n}{2})=\mathcal{T}(\textbf{W},p)$. First,
sort the edges $(\\{i,j\\})_{i\neq j}$ of $G(\textbf{W},p)$ by decreasing
order of their capacities $(E_{\\{i,j\\}})_{i\neq j}$. At step $1$,
$\mathcal{G}(\textbf{W},p,1)=G(\textbf{W},p)$. If deleting the first edge in
the order disconnects a connected component of $\mathcal{G}(\textbf{W},p,1)$
then keep it. Otherwise, delete it. This gives $\mathcal{G}(\textbf{W},p,2)$.
Then, move on to the next edge and do the same. Continue like this by either
keeping or deleting each edge consecutively. This procedure ensures that all
the graphs $\mathcal{G}(\textbf{W},p,i)$ have the same number of connected
components and only their number of cycles decreases. We call this the edges
deletion algorithm, also known as bombing optimization (Braunstein, Wu, Chen,
Buldyrev, Kalisky, Sreenivasan, Cohen, Lopez, Havlin, and Stanley (2007)). It
is easy to see that this procedure yields a forest in the end since we are
removing all the cycles from the graph. Moreover, by construction,
$\mathcal{T}(\textbf{W},p)$ is the minimum spanning forest of
$G(\textbf{W},p)$ with respect to the capacities $(E_{\\{i,j\\}})_{i\neq j}$
because we delete the largest capacities first. Hence,
$\mathcal{T}(\textbf{W},+\infty)$ is the minimum spanning tree of the complete
graph with respect to the capacities $(E_{\\{i,j\\}})_{i\neq j}$. The diameter
of a graph is the largest graph distance (number of edges) between two of its
nodes. If the graph is not connected its diameter is the maximum of the
diameters of its connected components. The purpose of this paper is the study
of the diameter of $\mathcal{T}(\textbf{W},+\infty)$. Before going further in
the discussions, we introduce some notations.

###  1.2 Notations and definition of the exploration process

We start by giving another definition of the graphs and defining the
exploration processes we will work with. We use exactly the same definition we
already used in Safsafi (2020). Consider $n\in\mathbb{N}$ vertices labeled
$1,2..,n$. For a vector of weights $\textbf{W}=(w_{1},w_{2},..w_{n})$, where
$0<w_{n}\leq w_{n-1}\leq...\leq w_{1}$, we create the inhomogeneous random
graph associated to W and to $p\leq+\infty$ in the following way:

Each potential edge $\\{i,j\\}$ is in the graph with probability
$1-e^{-w_{i}w_{j}p}$ independently from everything else. This gives a random
graph that we call the rank-1 inhomogeneous random graph associated to W and
$p\leq+\infty$. This construction yields graphs with the marginal distribution
of the sequence $(G(\textbf{W},p))_{p\in[0,+\infty]}$ presented previously. We
will keep both those two graphs construction methods in mind in this article,
and switch between the two depending on our needs.

Before stating the main theorem, we define an exploration process for
$G(\textbf{W},p)$ seen as a graph from the sequence
$(G(\textbf{W},p))_{p\in[0,+\infty]}$ for a fixed $p$. This process is based
on an "horizontal" exploration of the graph, called the breadth-first walk
(BFW). Write:

$\ell_{n}=\sum_{i=1}^{n}w_{i},$

and recall that the weights depend implicitly on $n$. We say that a tree is
spanning a graph if it has the same set of nodes and a subset of its edges.
The BFW also naturally yields a spanning forest of $G(\textbf{W},p)$. That is
a sequence of spanning trees of the connected component of $G(\textbf{W},p)$.

For each potential edge $\\{i,j\\}$ recall the definition of $E_{\\{i,j\\}}$
from the previous subsection. The BFW operates by steps, define the following
sets of vertices. A vertex is always in exactly one of those sets:

  * •

$(\mathcal{U}(i))_{1\leq i\leq n}$ is the sequence of sets of unexplored
vertices at each step.

  * •

$(\mathcal{D}(i))_{1\leq i\leq n}$ is the sequence of sets of discovered but
not yet explored vertices at each step.

  * •

$(\mathcal{F}(i))_{1\leq i\leq n}$ is the sequence of sets of explored
vertices at each step.

First, choose a vertex $i$ with probability:

$\mathbb{P}(v(1)=i)=\frac{w_{i}}{\ell_{n}},$

and call it $v(1)$. Let $\mathcal{V}$ be the set of all vertices labels, and
$\mathcal{U}(1)=\mathcal{V}\setminus\\{v(1)\\}$, $\mathcal{D}(1)=\\{v(1)\\}$.
At step $2$, $v(1)$ is explored. The vertices $j$ that are unexplored and such
that $E_{\\{j,v(1)\\}}\leq p$ become discovered but not yet explored. We call
them children of $v(1)$. Let $c(1)$ be the number of children of $v(1)$.
Denote their labels by $(v(2),v(3),...,v(c(1)+1)$ in increasing order of their
$E_{\\{j,v(1)\\}}$’s. For $i\geq 1$, denote the set $\\{v(1),v(2),...,v(i)\\}$
by $\mathcal{V}_{i}$. Hence, at step $2$ we have:

  * •

$\mathcal{U}(2)=\mathcal{V}\setminus\mathcal{V}_{c(1)+1}$.

  * •

$\mathcal{D}(2)=\mathcal{V}_{c(1)+1}\setminus\mathcal{V}_{1}$.

  * •

$\mathcal{F}(2)=\mathcal{V}_{1}$.

Now, at the step $3$, $v(2)$ becomes explored. The vertices $j$ that are
unexplored and such that $E_{\\{j,v(2)\\}}\leq p$ become discovered but not
yet explored. We call them children of $v(2)$, and we denote their labels by
$\\{v(c(1)+2),v(c(1)+3)...,v(c(1)+c(2)+3)\\}$. The BFW continues like this. At
step $i+1$ node $v(i)$ becomes explored. If the set of discovered but not yet
explored nodes become empty at some step $i$, this means that the exploration
of a connected component is finished. In that case, we move on to the next
step by choosing a vertex $j$ with probability proportional to its weight
$w_{j}$ among the unexplored vertices (like we did for $v(1)$). We call this a
size-biased sampling. The spanning forest associated to the the BFW is created
by considering each node without a parent as a root, and adding only the edges
between parent nodes and their children. We call the trees in that forest the
exploration trees. By construction, exploration trees are spanning trees of
the connected components of $G(\textbf{W},p)$. We say that a connected
component is discovered at step $i$ if its first node discovered by the BFW is
$v(i)$. Similarly, we say that a connected component is explored at step $i$
if its last node that becomes explored in the BFW is $v(i)$.

Generally, let $c(i)$ be the number of children of the node labeled $v(i)$.
The exploration process associated to the BFW above is defined as follow, for
$n-1\geq i\geq 0$:

$\displaystyle L^{\prime}_{0}$ $\displaystyle=1,$ $\displaystyle
L^{\prime}(i+1)$ $\displaystyle=L^{\prime}_{i}+c(i+1)-1.$

The reflected exploration process is defined by

$\displaystyle L_{0}$ $\displaystyle=1,$ $\displaystyle L(i+1)$
$\displaystyle=\max(L_{i}+c(i+1)-1,1).$

Figure 2: Example of a graph with ordered nodes. The integers correspond to
the order in the exploration process. The edges in red correspond to the edges
of the exploration trees. The labels of the nodes are not represented. Figure
3: The exploration process of the graph in Figure 2.

The increment of the process $L^{\prime}$ at step $i$ is the number of nodes
added to the set of discovered nodes in the BFW at step $i$. This number is at
least $-1$ if the node being explored has no children. The process
$L^{\prime}$ contains a lot of the information about $G(\textbf{W},p)$. For a
more indepth discussion on those process we refer the reader to the related
part in Safsafi (2020).

The order of appearance of the nodes in the exploration process corresponds to
a size-biased sampling. Formally, we have:

######  Lemma 1.

With the notations presented above, for:

$i\in\\{0,1,...,n-1\\},$

and

$j\in\\{0,1,...,n\\},$

we have:

$\displaystyle\mathbb{P}\left(v(1)=j\right)=\frac{w_{j}}{\ell_{n}}.$
$\displaystyle\mathbb{P}\left(v(i+1)=j\quad|\mathcal{V}_{i}\right)=\frac{w_{j}\mathbbm{1}(j\not\in\mathcal{V}_{i})}{\ell_{n}-\sum\limits_{k=1}^{i}w_{v(k)}}.$

The proof of this fact is present in Safsafi (2020). We will assume the
following conditions on W in the entire article.

######  Conditions 1.

There exists some positive random variable $W$ such that:

  1. (i)

The distribution of a uniformly chosen weight $w_{X}$ converges weakly to $W$.

  2. (ii)

$\mathbb{E}[W^{3}]<\infty$.

  3. (iii)

$\mathbb{E}[W^{2}]=\mathbb{E}[W]$.

  4. (iv)

$\ell_{n}=\mathbb{E}[W]n+o(n^{2/3})$.

  5. (v)

$\sum\limits_{k=1}^{n}w_{k}^{2}=\mathbb{E}[W^{2}]n+o(n^{2/3})$.

  6. (vi)

$\sum\limits_{k=1}^{n}w_{k}^{3}=\mathbb{E}[W^{3}]n+o(1)$.

  7. (vii)

$\max_{i\leq n}w_{i}=o(n^{1/3})$.

######  Conditions 2.

All the Conditions in 1 hold, and moreover:

  1. (viii)

$\sum\limits_{k=1}^{n}w_{k}^{4}=\mathbb{E}[W^{4}]n+o(1),$ and
$\mathbb{E}[W^{4}]<\infty$.

We refer the reader to Safsafi (2020) for a more in-depth discussion of these
conditions. Here, we only draw attention to two facts. Firstly, condition
$(viii)$ is only present for technical reasons in Safsafi (2020). It is not
necessary for the main theorem to hold. And we will get rid of this condition
in a subsequent article. Secondly, an important case to keep in mind is when
$(w_{1},w_{2},...,w_{n})$ are realizations of random variables
$(W_{1},W_{2},...,W_{n})$ which are i.i.d. with distribution $W$. In that case
the conditions can be seen as consequences of convergence theorems and hold
almost surely.

We also define the size of a connected component $\mathcal{C}$, with vertices
set $V(\mathcal{C})$, as the number of vertices in $\mathcal{C}$. The distance
between two vertices of $\mathcal{C}$ is the number of edges in the smallest
(in number of edges) path between them. We also define the weight of
$\mathcal{C}$ as:

$\sum_{i\in V(\mathcal{C})}w_{i}.$

We call surplus (or excess) of $\mathcal{C}$ the number of edges that have to
be removed from it in order to make it a tree. For instance, the surplus of a
tree is $0$, and the surplus of a cycle is $1$. We can now state our two main
theorems.

######  Theorem 2.

Suppose that Conditions 2 are verified. For any
$\ell_{n}^{4/3}-\ell_{n}^{1/3}\geq f_{n}\geq 0$ the diameter of
$\mathcal{T}(\textbf{W},\frac{1}{\ell_{n}}+\frac{f_{n}}{\ell_{n}^{4/3}})$,
denoted by
$\textnormal{diam}(\mathcal{T}(\textbf{W},\frac{1}{\ell_{n}}+\frac{f_{n}}{\ell_{n}^{4/3}}))$,
verifies111The notation $\Theta(n^{\frac{1}{3}})$ means that there exists two
constants $\epsilon>0$ and $A>0$ and an $N>0$, such that for any $n\geq N$ we
have the diameter is larger than $\epsilon n^{1/3}$ and smaller than
$An^{1/3}$.:

$\mathbb{E}\left[\textnormal{diam}\left(\mathcal{T}\left(\textbf{W},\frac{1}{\ell_{n}}+\frac{f_{n}}{\ell_{n}^{4/3}}\right)\right)\right]=\Theta(n^{\frac{1}{3}}).$

We will further discuss our choice of parameter $f_{n}$ in this theorem in the
next sections. The second theorem is related to typical distances in those
minimum spanning trees.

######  Theorem 3.

Suppose that Conditions 2 are verified. For $c>1$ and a sequence of parameters
$\tilde{p}_{n}\geq\frac{c}{\ell_{n}}$, let $(U_{f_{n}},V_{f_{n}})$ be two
uniformly randomly drawn nodes from the largest tree in
$\mathcal{T}(\textbf{W},\tilde{p}_{n})$, and let $d(U_{f_{n}},V_{f_{n}})$ be
the distance between them in $\mathcal{T}(\textbf{W},\tilde{p}_{n})$. We have
:

$\mathbb{E}[d(U_{f_{n}},V_{f_{n}})]=\Theta(n^{1/3}).$

One important thing that will be clear from our proofs is that those theorems
hold if we replace the inhomogeneous minimum spanning trees by other types of
trees verifying an inclusion property. Let $a>0$ and $(G_{p})_{p\geq a}$ be an
increasing process of graphs for inclusion. We say that the sequence of
forests $(T_{p})_{p\geq a}$ is an increasing process of spanning forests of
$(G_{p})_{p\geq a}$ if, for any $p\geq a$, $T_{p}$ is a spanning forest of
$G_{p}$, and the process $(T_{p})_{p\geq a}$ is increasing for inclusion.

By definition $(\mathcal{T}(\textbf{W},p))_{p\geq 0}$ is an increasing process
of spanning forests of $(G(\textbf{W},p))_{p\geq 0}$. A direct corollary of
our proofs is the following :

######  Corollary 3.1.

Theorems 2 and 3 still hold if we replace the trees
$(\mathcal{T}(\textbf{W},p))_{p\geq\frac{1}{\ell_{n}}}$ by any increasing
process of spanning forests of $(G(\textbf{W},p))_{p\geq\frac{1}{\ell_{n}}}$.

This corollary is true because our proofs only use the fact that
$(\mathcal{T}(\textbf{W},p))_{p\geq 0}$ in an increasing process of spanning
forests of $(G(\textbf{W},p))_{p\geq 0}$. And we never use any other property
proper to $(\mathcal{T}(\textbf{W},p))_{p\geq 0}$.

This is thus a generalization of Theorems 2 and 3. However, we emphasise the
fact that given an increasing process of graphs for inclusion. An increasing
process of spanning trees is uniquely determined by the spanning forest of the
first graph in the process. The condition of being an increasing process of
spanning trees is thus very strong and does not allow for much freedom in the
choice of the process. Still, this is a nice addition that will be used in
this article to tackle a conjecture from statistical physics. And we hope that
it will find use in later work.

###  1.3 Further discussion and related work in statistical physics

Addario-Berry et al. (2009) already showed a similar result to Theorem 2 with
$\textbf{W}=(1,1,...,1)$. In this case the inhomogeneous random graph is in
fact an Erdős-Rényi random graphs. Our theorem is thus a generalization of
theirs. It is also another hint at the fact that when the weights of rank-1
inhomogeneous random graphs verify a third moment condition, which corresponds
to Conditions 1, then their asymptotic behavior is similar to Erdős-Rényi
random graphs. Meaning that the inhomogeneity disappears asymptotically. Such
behavior was already remarked for other asymptotic properties (see for
instance Bhamidi et al. (2010)).

Another interesting result is in Addario-Berry et al. (2017) where the authors
showed the existence of a measured metric space that is a scaling limit of the
minimum spanning tree associated to Erdős-Rényi random graph with distances
rescaled by $n^{-1/3}$. In that article the concentration results that gave
the order of the diameter of the minimum spanning tree corresponding to
$\textbf{W}=(1,1,...,1)$ were crucially used. A similar result was obtained
for $3$-regular graphs with i.i.d. capacities on their edges in Addario-Berry
and Sen (2019). We will do the same for general weights verifying Conditions 1
in a subsequent article.

In an even more general setting, one can ease the Conditions 2. A large body
of work (Chen, López, Havlin, and Stanley (2006), Braunstein et al. (2007),
Stegehuis, van der Hofstad, Janssen, and van Leeuwaarden (2017), van der
Hofstad, Kliem, and van Leeuwaarden (2018), Broutin, Duquesne, and Wang
(2020)) is interested in weights related to power law distributions, the so
called scale-free model. In that case the diameter is not expected to be of
order $n^{1/3}$. If we suppose that the weights are drawn from a distribution
with power law tail with parameter $4\geq\alpha>3$, then intuitive arguments
suggest that the diameter of the minimum spanning tree should be of order
$n^{\frac{\alpha-3}{\alpha-1}}$ (see Broutin et al. (2020)). The scaling limit
of such trees should also be mutually singular from one another for different
values of $\alpha$. Some of the tools presented here could be useful to prove
results for weights with power law distributions. However, more work is
required to prove those conjectures.

The model presented here is closely related and generally called the Norros-
Reitu model (Norros and Reittu (2006)) altough it is slightly different from
the first model proposed by Norros and Reitu, since their model allows for
multigraphs. This has no incidence on our results. In fact, our model is more
closely related to the multiplicative coalescent introduced by Aldous in
Aldous (1997), and further studied in Aldous and Limic (1998) by Aldous and
Limic. Moreover, the results we present for this model also hold for
equivalent models, in the sense of Janson (2010). For instance, Chung-Lu
(Chung and Lu (2006)) proposed a random graph with prescribed expected
degrees. In that model two nodes $\\{i,j\\}$ are connected with probability:

$p_{i,j}=\frac{w_{i}w_{j}}{\ell_{n}}.$

It supposes that $\max_{i,j}(w_{i}w_{j})\leq\ell_{n}$. The following classical
theorem (proved in Bollobás, Janson, and Riordan (2007)) holds for all those
graph models and is crucial in understanding the evolution of the graph
process $(G(\textbf{W},p))_{p\geq 0}$.

######  Theorem 4.

Recall that $\tilde{p}_{n}=\frac{c}{\ell_{n}}$. Take
$G(\textbf{W},\tilde{p}_{n})$ and suppose that Conditions 1 are verified, then
the following results hold with high probability 222We say that a sequence of
events $E_{n}$ holds with high probability if
$\lim_{n\rightarrow\infty}\mathbb{P}(E_{n})=1$.:

  * •

Subcritical regime If $c<1$ then the largest connected component is of size
$o(n)$.

  * •

Supercritical regime If $c>1$ then the largest connected component is of size
$\Theta(n)$ and for any $i>1$ the $i$-th largest connected component is of
size $o(n)$.

  * •

Critical regime If $c=1$ then for any $i\geq 1$ the $i$-th largest connected
component is of size $\Theta(n^{2/3})$.

A simulation-based conjecture from statistical physics (Chen et al. (2006), Wu
et al. (2006), Braunstein et al. (2007)) is the following: Consider the
largest component of $G(\textbf{W},\tilde{p}_{n})$ for $c>1$. Put i.i.d.
capacities derived from some continuous distribution on the edges of that
component. Then typical distances in the minimal spanning tree constructed on
the largest component with those i.i.d. capacities scale like $n^{1/3}$. Here
typical distances mean distance between two uniformly drawn nodes from the
tree. First, notice that as long as the distribution used is atomless, it has
no incidence on the distribution of the geometry of the tree obtained. Indeed,
only the relative order of the edge capacities is relevant for the geometry of
the minimum spanning tree. Hence, putting i.i.d. capacities on the edges
amounts to taking a uniform random order on them for our purpose. In order to
prove this conjecture, it is sufficient to prove a result similar to Theorem 3
but for the type of minimum spanning trees present in the statistical physics
literature. In fact, this minimum spanning tree is not that much different
from the inhomogeneous minimum spanning trees that we study in this article.
One can see that, with a little more work, the result from Janson (2010) can
be used to show that if Theorem 3 is true, then a similar theorem also holds
for the minimum spanning trees constructed from i.i.d capacities on the giant
component of supercritical inhomogeneuous random graphs. However, for clarity,
after proving Theorem 3, we will prove a modified version of it to show the
conjecture from statistical physics using our results. We thus prove the
following Theorem:

######  Theorem 5.

Suppose that Conditions 2 are verified. For $c>1$, and a sequence of
parameters $\tilde{p}_{n}\geq\frac{c}{\ell_{n}}$, put i.i.d. capacities with
an atomless distribution on the edges of the graphs
$(\mathcal{G}(\textbf{W},\tilde{p}_{n}))_{n\geq 1}$. Let
$\mathcal{T}^{\prime}(\textbf{W},\tilde{p}_{n})$ be the minimum spanning
forest of $\mathcal{G}(\textbf{W},\tilde{p}_{n})$ corresponding to those edge
capacities. Let $(U_{f_{n}},V_{f_{n}})$ be two uniformly randomly drawn nodes
from the largest tree in $\mathcal{T}^{\prime}(\textbf{W},\tilde{p}_{n})$, and
let $d(U_{f_{n}},V_{f_{n}})$ be the distance between them in
$\mathcal{T}^{\prime}(\textbf{W},\tilde{p}_{n})$. We have :

$\mathbb{E}[d(U_{f_{n}},V_{f_{n}})]=\Theta(n^{1/3}).$

Another closely related conjecture concerns the power law distribution case.
It is generally also conjectured that typical distances in the minimum
spanning tree with i.i.d. capacities on the edges of largest components of
graphs with nodes weights following a distribution with a power law tail of
parameter $4>\alpha>3$, either in inhomogeneous random graphs as studied here,
or in the configuration model (Braunstein et al. (2007)), scale like
$n^{\frac{\alpha-3}{\alpha-1}}$. Proving the existence of a non-trivial
scaling limits for $\mathcal{T}(\textbf{W},+\infty)$ when we change Conditions
1 to conditions pertaining to power law distribution would also prove such a
conjecture. A first step in that direction was done very recently in Bhamidi
and Sen (2020). The authors proved that the diameter of such trees is in fact
of order $n^{\frac{\alpha-3}{\alpha-1}}$ in the inhomogeneous case and they
even showed the existence of a non-trivial scaling limit for those trees.
However, their work supposes restrictive conditions on the distribution other
than just having power law tail. Thus, the general case remains open.

Figure 4: A minimum spanning tree built on the giant component of a scale-free
supercritical inhomogeneous random graph with parameter $\alpha=3.5$. The edge
capacities are i.i.d.. Nodes are coloured from largest in red to smallest in
dark-blue. Node sizes are proportionnal to the square of their degrees.

Figure 5: A minimum spanning tree built on the giant component of a
supercritical inhomogeneous random graph with node weights having finite third
moments. The edge capacities are i.i.d.. Nodes are coloured from largest in
red to smallest in dark-blue. Node sizes are proportionnal to the square of
their degrees.

Lastly in this introduction, we remind the reader of Bernstein’s inequality
(Bernstein (1924), Boucheron, Lugosi, and Massart (2013)). This inequality
will be used through this article in order to prove some concentration bounds.

######  Lemma 6.

Let $X_{1},X_{2},...,X_{n}$ be i.i.d. random variables with finite second
moment. Suppose that $|X_{i}|\leq M$, for all $i$. Then for any positive
number $x$:

$\mathbb{P}\left(\middle|\sum_{i\geq
1}^{n}(X_{i}-\mathbb{E}[X_{i}])\middle|\geq x\right)\leq
2\exp\left(\frac{-\tfrac{1}{2}x^{2}}{\sum_{i=1}^{n}\mathbb{E}\left[X_{i}^{2}\right]+\tfrac{1}{3}Mt}\right).$

##  2 First ingredients of the proof

For $p\geq 0$. Any component of $G(\textbf{W},p)$ that is a tree is also a
component of $\mathcal{T}(\textbf{W},p)$. Since
$\mathcal{T}(\textbf{W},p)\subseteq\mathcal{T}(\textbf{W},+\infty)$, the
diameter of any tree component of $G(\textbf{W},p)$ is a lower bound on
$\textnormal{diam}(\mathcal{T}(\textbf{W},+\infty))$. The following theorem is
a simple corollary of the much more general convergence result in Theorem
$2.4$ of Broutin et al. (2020).

######  Theorem 7.

There exists $\epsilon>0$ and $\epsilon^{\prime}>0$ such that for all $n$
large enough the largest connected component of
$G(\textbf{W},\frac{1}{\ell_{n}})$ is a tree of diameter at least
$\epsilon^{\prime}n^{1/3}$ with probability at least $\epsilon$.

Theorem 7 proves that there exist a constant $\epsilon>0$ such that
$\mathbb{E}[\textnormal{diam}(\mathcal{T}(\textbf{W},+\infty))]\geq\epsilon
n^{1/3}$. The rest of this paper is dedicated to proving the upper bound of
Theorem 2.

###  2.1 The phase transition

The edge deletion algorithm provides a coupling between
$\mathcal{T}(\textbf{W},+\infty)$ and the graph $G(\textbf{W},+\infty)$.
Hence, by studying the evolution of the diameter of the graphs in
$(G(\textbf{W},p))_{p\in[0,+\infty]}$ we will be able to prove Theorem 2. As a
first step, we want to know what are the important values of $p$ in this
process. That question was partly answered in Theorem 4. We see that there is
a phase transition at $p=\frac{1}{\ell_{n}}$. It turns out that
$p=p_{f}=\frac{1}{\ell_{n}}+\frac{f}{\ell_{n}^{4/3}}$, with $f\in\mathbb{R}$,
constitutes a phase transition "window" for the size of the connected
components sizes. In that window, the size and weight of the largest component
increase smoothly. This is the so called critical regime. It is thus natural
to investigate this critical regime in order to prove Theorem 2.

We will show that the diameter of $\mathcal{T}(\textbf{W},p_{f})$ is a
$O(n^{1/3})$, when $p=p_{f}=\frac{1}{n}+\frac{f}{n^{4/3}}$ with $f>0$ a large
constant. Then it only grows by $O(n^{1/3})$ when $p$ becomes strictly larger
than $\frac{1}{n}$. The increase of the diameter in the supercritical phase is
easy to study, the main problem is to show that when we cross the critical
regime, $p_{f}=\frac{1}{\ell_{n}}+\frac{f_{n}}{\ell_{n}^{4/3}}$ with $f_{n}$
going to infinity, the diameter remains of order $n^{1/3}$. The value
$f^{\prime}_{n}=\frac{\ell_{n}^{1/3}}{\log(n)}$ which gives
$p_{f^{\prime}_{n}}=\frac{1}{\ell_{n}}+\frac{1}{\log(n)\ell_{n}}$ constitutes
the pivotal moment where we will switch arguments: $p_{f^{\prime}_{n}}$ is
chosen like this because it is neither a critical nor a real supercritical
value. We say that it is in the barely supercritical regime. In the rest of
this section we will take Theorems 8 and 9 for granted and prove Theorem 2.
The proofs of these theorems will be the focus of the rest of the paper.

Notation: In the remainder of the article we drop the $n$ from $f_{n}$ for
clarity, $f$ will always be the critical parameter, moreover we will always
assume $f=o(n^{1/3})$ and $f\geq F$, where $F>0$ is a constant independent of
$n$ which is large enough for all our theorems to be true. Similarly
$A,A^{\prime},A^{\prime\prime},...\in\mathbb{R}^{+}$ will always be large
constants independent of $n$. And
$\epsilon,\epsilon^{\prime},...\in\mathbb{R}^{+}$ will always be small
constants independent of $n$.

######  Theorem 8.

Assume Conditions 2, there exists a positive constant $A>0$ such that: With
probability at least $(1-\frac{1}{n})$, the largest component,
$H(\textbf{W},p_{f^{\prime}_{n}})$, of $G(\textbf{W},p_{f^{\prime}_{n}})$ has
total weight at least $\frac{n}{A\log(n)}$ and every other connected component
has total weight at most $A\log(n)^{1/2}n^{1/2}$ and longest path of length
less than $A\log(n)^{1/4}n^{1/4}$.

######  Theorem 9.

Assume Conditions 2, then:

$\mathbb{E}[\text{diam}(H(\textbf{W},p_{f^{\prime}_{n}}))]=O(n^{1/3})$

###  2.2 The supercritical phase

Here we take Theorems 8 and 9 for granted. Let $\mathcal{C}$ be a connected
component, with vertices set $V(\mathcal{C})$ and edge set $D(\mathcal{C})$ ,
and suppose that $\mathcal{C}$ is not the largest connected component of
$G(\textbf{W},p_{f^{\prime}_{n}})$. Let $\\{I,J\\}$ be the random edge with
exactly one endpoint (say $I$) in $\mathcal{C}$ and with minimal capacities
$E_{\\{I,J\\}}$ among edges with exactly one endpoint in $\mathcal{C}$. By
construction, $\\{I,J\\}$ will necessarily be in
$\mathcal{T}(\textbf{W};+\infty)$. We want to calculate $\mathbb{P}(J\in
V(H(\textbf{W},p_{f^{\prime}_{n}})))$, the probability that the other endpoint
of the edge $\\{I,J\\}$ lies in the largest component
$H(\textbf{W},p_{f^{\prime}_{n}})$ with vertices set
$V(H(\textbf{W},p_{f^{\prime}_{n}}))$ and edge set
$D(H(\textbf{W},p_{f^{\prime}_{n}}))$. Recall that for any couple $\\{i,j\\}$,
$E_{\\{i,j\\}}$ is an exponential random variable of parameter $w_{i}w_{j}$.
So if we fix $\\{i,j\\}$, by classical results on exponential random
variables:

$\mathbb{P}\left(\forall l\neq i,l\neq j\quad
E_{\\{i,j\\}}<E_{\\{i,l\\}}\right)=\frac{w_{j}}{\sum_{k=1}^{n}w_{k}}.$

Similarly, write:

$\textbf{U}=\left\\{i\in V(\mathcal{C}),\exists j\in
V(H(\textbf{W},p_{f^{\prime}_{n}})),\forall
l\in(\mathcal{V}\setminus(V(\mathcal{C})\cup\\{j\\})\;E_{\\{i,j\\}}<E_{\\{i,l\\}}\right\\}.$

Then:

$\displaystyle\mathbb{P}\left(\textbf{U}|(V(H(\textbf{W},p_{f^{\prime}_{n}})),V(\mathcal{C}))\right)=\frac{\sum_{k\in
V({H(\textbf{W},p_{f^{\prime}_{n}}))}}{w_{k}}}{\sum_{k^{\prime}=1}^{n}w_{k^{\prime}}-\sum_{k^{\prime\prime}\in
V(\mathcal{C})}w_{k^{\prime\prime}}}.$

Which implies that:

$\mathbb{P}\left(J\in
V(H(\textbf{W},p_{f^{\prime}_{n}}))|(V(H(\textbf{W},p_{f^{\prime}_{n}})),V(\mathcal{C}))\right)=\frac{\sum_{k\in{H(\textbf{W},p_{f^{\prime}_{n}})_{V}}}{w_{k}}}{\sum_{k^{\prime}=1}^{n}w_{k^{\prime}}-\sum_{k^{\prime\prime}\in
V(\mathcal{C})}w_{k^{\prime\prime}}}.$ (1)

By Theorem 8 and Equation (1), we get for $n$ large enough:

$\displaystyle 1-\mathbb{P}\left(J\in
V(H(\textbf{W},p_{f^{\prime}_{n}}))\right)$ $\displaystyle\leq
1-\frac{n}{A\log(n)(n-A\log(n)^{1/2}n^{1/2})}-\frac{1}{n}$ $\displaystyle\leq
1-\frac{2}{A\log(n)},$

If $J$ is not in $V(H(\textbf{W},p_{f^{\prime}_{n}}))$, then $J$ lies in
another connected component $\mathcal{C}^{\prime}$, with vertix set
$V(\mathcal{C}^{\prime})$ and edge set $D(\mathcal{C}^{\prime})$. So the
longest path of the newly created component will be at most
$2A\log(n)^{1/4}n^{1/4}$ with probability at least $1-\frac{2}{A\log(n)}$. Let
$\\{I^{\prime},J^{\prime}\\}$ be the edge with the smallest capacities with
exactly one endpoint $I^{\prime}$ in the newly created connected component
$\mathcal{C}^{\prime\prime}$ which is the concatenation of $\mathcal{C}$ and
$\mathcal{C}^{\prime}$ through the edge $\\{I,J\\}$. By the same argument as
before, conditionally on the event $F$ that $J$ is not in
$V(H(\textbf{W},p_{f^{\prime}_{n}}))$, we get for $n$ large enough:

$\displaystyle 1-\mathbb{P}\left(J^{\prime}\not\in
V(H(\textbf{W},p_{f^{\prime}_{n}})))|F\right)$ $\displaystyle\leq
1-\frac{n}{\log(n)(n-2A\log(n)^{1/2}n^{1/2})}-\frac{1}{n}$ $\displaystyle\leq
1-\frac{2}{A\log(n)}.$

By an immediate induction, for any $r_{n}$ small enough, the probability that
$\mathcal{C}$ is in a component of longest path larger than
$r_{n}A\log(n)^{1/4}n^{1/4}$ when it connects to the largest connected
component is at most $(1-\frac{2}{A\log(n)})^{r_{n}}$. By taking
$r_{n}=A(\log(n))^{2}$, it follows, using the inequality

$\left(1-\frac{2}{A\log(n)}\right)\leq\exp\left(\frac{-2}{A\log(n)}\right),$

that the probability that the longest path of $\mathcal{C}$ reaches
$A^{2}\log(n)^{9/4}n^{1/4}$ before connecting to the largest component is less
than $\frac{1}{n^{2}}$. Since $\mathcal{C}$ was arbitrary, and since there are
at most $n$ such components. We get by the union bound that the probability
that there is a component that has a path longer than
$A^{2}\log(n)^{9/4}n^{1/4}=o(n^{1/3})$ when it connects to the largest
connected component is at most $\frac{1}{n}$.

In order to link the diameters of nested graphs we use the following lemma
(Also used in Addario-Berry et al. (2009)).

######  Lemma 10.

Let $H^{\prime}$ and $H$ be two connected graphs such that $H^{\prime}\subset
H$. Then

$diam(H)\leq diam(H^{\prime})+2lp(H(V-V(H^{\prime})))+2.$

Here $lp$ stands for longest path and $H(V-V(H^{\prime}))$ is the graph $H$
from which we deleted the nodes of $H^{\prime}$ and any edge that had at least
one endpoint in $H^{\prime}$.

###### Proof.

In order to show the lemma it is sufficient to show that between any two
vertices $H$ there exist a path of length at most than
$diam(H^{\prime})+2lp(H(V-V(H^{\prime})))+2$. Let $x,y$ be two vertices of
$H$, one can create a path from $x$ to $y$ in the following way.

  * •

There exists a path $\pi_{1}$ between $x$ and a vertex of $H^{\prime}$ that
has length at most $lp(H(V-V(H^{\prime})))+1$, let $x^{\prime}$ be the arrival
vertex of this path.

  * •

There exists a path $\pi_{2}$ between $y$ and a vertex of $H^{\prime}$ that
has length at most $lp(H(V-V(H^{\prime})))+1$, let $y^{\prime}$ be the arrival
vertex of this path.

  * •

There exists a path $\pi_{3}$ between $x^{\prime}$ and $y^{\prime}$ inside
$H^{\prime}$ that has length at most $diam(H^{\prime})$.

Concatenating the three paths $\pi_{1}$, $\pi_{2}$ and $\pi_{3}$ provides the
desired path.

∎

Lemma 10 and the discussion above imply that:

######  Theorem 11.

Under conditions 2:

$\mathbb{E}\left[\textnormal{diam}(\mathcal{T}(\textbf{W};+\infty))-\textnormal{diam}(\mathcal{T}(\textbf{W};f^{\prime}_{n}))\right]=O(\log(n)^{9/4}n^{1/4}).$

Theorem $1$ follows from this theorem and Theorem 9. Now what is left is
proving Theorems 8 and 9. This is what we will do in the rest of the paper.

###  2.3 Known results

Here we remind the reader of the main theorems in Safsafi (2020) that will be
used in this article. Let:

$C=\frac{\mathbb{E}[W^{3}]}{\mathbb{E}[W]}\geq 1.$

######  Theorem 12.

There exists a constant $A>0$, such that for any $1>\epsilon^{\prime}>0$,
$1\geq\epsilon>0$, and $f=o(n^{1/3})$ large enough with probability at least:

$1-A\exp\left(\frac{-f^{\epsilon/2}}{A}\right),$

all the following events occur in $G(\textbf{W},p_{f})$:

  * •

The size of the largest component is in the interval

$\left[\frac{2(1-\epsilon^{\prime}/2)f\ell_{n}^{2/3}}{C},\frac{2(1+\epsilon^{\prime}/2)f\ell_{n}^{2/3}}{C}\right].$

  * •

Every other connected component has size less than
$\frac{A\ell_{n}^{2/3}}{f^{1-\epsilon}}$.

  * •

The weight of the largest component is in the interval

$\left[\frac{2(1-\epsilon^{\prime})f\ell_{n}^{2/3}}{C},\frac{2(1+\epsilon^{\prime})f\ell_{n}^{2/3}}{C}\right].$

  * •

Every other connected component has weight less than
$\frac{(1+\epsilon^{\prime})A\ell_{n}^{1/3}}{f^{1-\epsilon}}$.

  * •

The surplus of the largest connected component is less than $Af^{3}$.

  * •

The surplus of any other connected component is less than $Af^{\epsilon}$.

This theorem contains many important statements for our proof. It gives bounds
on the size, weight and surplus of the largest connected component of rank-1
inhomogeneous random graphs in the critical window, and also of its small
components. For instance, by taking $f=f^{\prime}_{n}$ in the above theorem we
get the statement about the weights in Theorem 8. The analysis in Safsafi
(2020) also provides bounds on the time the giant component is discovered
during the exploration process. These results show a large part of Theorems 8
and 9. However they are not enough to bound the diameter of the graph.
Information about the length of paths in the graph is still lacking. Although
Theorem 12 contains a bound on the surplus of each connected component of
$G(\textbf{W},p_{f^{\prime}_{n}})$, it is not sufficient to prove upper bounds
on the height of any spanning trees of the connected components in order to
finish the proof. This is due to the fact that the surplus of the connected
components of $G(\textbf{W},p_{f^{\prime}_{n}})$ is too large. In the
remainder of the paper we will use a "snapshot" trick to fix this problem.

##  3 Dealing with the small components

In order to bound the diameter of a graph using its excess and its height we
will use the following lemma.

######  Lemma 13.

Let $G$ be a connected graph of excess $q$ and such that there exist a
spanning tree $T$ of this graph of height $h$, then the longest path of the
graph is of length at most

$2h(q+1)+q.$

###### Proof.

Let $\\{D_{1},D_{2},D_{3},....\\}$ be the set of edge-disjoint paths of
maximum lengths in $T$ taken in decreasing order of their lengths, if two
paths of the same length exist at some point we choose one of them
arbitrarily. We can create $G$ by adding the excess edges consecutively to
$T$.

Recursively, the first edge added will create a new longest path of length at
most $|D_{1}|+|D_{2}|+1\leq 4h+1$. The second edge added will at most create a
new longest path containing $D_{1}$,$D_{2}$ and $D_{3}$ and of length
$|D_{1}|+|D_{2}|+|D_{3}|+2\leq 6h+2$. Hence, a direct induction shows that
after adding $q$ excess edges the longest path we can have is of length
$2h(q+1)+q$. ∎

If we want to use this lemma, then bounding directly the height of the
exploration tree of the largest component of
$G(\textbf{W},p_{f^{\prime}_{n}})$ will not be enough to prove Theorem 9.
Indeed, Theorem 12 states that the excess of such a component is upper bounded
by $f_{n}^{{}^{\prime}3}=\frac{\ell_{n}}{\log(n)^{3}}$. This is already much
larger than the $n^{1/3}$ of Theorem 9. In order to circumvent this problem we
will use the following steps.

  1. 1.

Define a sequence of "snapshots", $(p_{f(i)})_{i\geq 0}$ such that:

$f(0)=F$

is a large constant, and

$f(i+1)=\frac{3}{2}f(i),$

for any $i\geq 0$.

  2. 2.

For every $i\geq 0$, let $\tilde{\mathcal{V}}_{i}$ be the set of nodes of the
largest connected component of $G(\textbf{W},p_{f(i+1)})$, and let
$G(\mathcal{V}\setminus\tilde{\mathcal{V}}_{i},p_{f(i+1)})$ be the sub-graph
of $G(\textbf{W},p_{f(i+1)})$ from which we have taken out the nodes of the
largest component of $G(\textbf{W},p_{f(i)})$ alongside any edge that has one
of those nodes as endpoint. Show that the diameter of this graph is bounded by
$\frac{A\ell_{n}^{1/3}}{f(i+1)^{1/4}}$ w.h.p. This will also prove Theorem 8.

  3. 3.

Show that the diameter of the largest component of $G(\textbf{W},p_{f(i)})$ is
smaller than $Af^{5}\ell_{n}^{1/3}$ w.h.p.

  4. 4.

Use the precedent steps to show that when moving from $G(\textbf{W},p_{f(i)})$
to $G(\textbf{W},p_{f(i+1)})$, the diameter of the graph does not increase
significantly. This will prove Theorem 9.

We provide the details for step $2$ in the present section, step $3$ in
section 4, and step $4$ in the last section.

###  3.1 Construction of the growth of small components

For $i\geq 1$, we want to bound the size, excess and diameter of the graph
comprised of $G(\textbf{W},p_{f(i+1)})$ from which we have taken out the
vertices of the largest component in $G(\textbf{W},p_{f(i)})$. Recall that we
denote the set of those vertices by $\tilde{\mathcal{V}}_{i}$, and that graph
by $G(\mathcal{V}\setminus\tilde{\mathcal{V}}_{i},p_{f(i+1)})$. Bounding this
diameter will allow us to bound the growth of the giant component when moving
from $G(\textbf{W},p_{f(i)})$ to $G(\textbf{W},p_{f(i+1)})$. Instead of
studying $G(\mathcal{V}\setminus\tilde{\mathcal{V}}_{i},p_{f(i+1)})$ from
scratch, we will show that w.h.p, that graph resembles the graph
$G(\mathcal{V}\setminus\tilde{\mathcal{V}}_{i+1},p_{f(i+1)})$ which is a
critical inhomogeneous random graph from which we have taken the largest
component, and which has already been studied extensively in Safsafi (2020).
Let $K(i,\epsilon^{\prime})$ be the following event:

  1. 1.

The size of the largest component of $G(\textbf{W},p_{f(i)})$ is in the
interval

$\left[\frac{2(1-\epsilon^{\prime}/2)f(i)\ell_{n}^{2/3}}{C}-\frac{\ell_{n}^{2/3}}{f(i)C},\frac{2(1+\epsilon^{\prime}/2)f(i)\ell_{n}^{2/3}}{C}\right].$

  2. 2.

The total weight of the largest connected component of
$G(\textbf{W},p_{f(i)})$ is in the interval

$\left[\frac{2(1-\epsilon^{\prime})f(i)\ell_{n}^{2/3}}{C},\frac{2(1+\epsilon^{\prime})f(i)\ell_{n}^{2/3}}{C}\right].$

By Theorems $1$ from Safsafi (2020), there exists a large constant $A>0$ such
that $K(i,\epsilon^{\prime})$ happens with probability at least:

$1-A\exp\left(\frac{-f(i)}{A}\right).$ (2)

Let $(\tilde{v}(1),\tilde{v}(2),..)$ be the ordered labels in the exploration
process of the graph
$G(\mathcal{V}\setminus\tilde{\mathcal{V}}_{i},p_{f(i+1)})$. Conditionally on
the nodes of the largest component $\tilde{\mathcal{V}}_{i}$,
$G(\mathcal{V}\setminus\tilde{\mathcal{V}}_{i},p_{f(i+1)})$ is an
inhomogeneous random graph with vertices label set
$\mathcal{V}\setminus\tilde{\mathcal{V}}_{i}$ and probability transition
$p_{f(i+1)}$. Moereover, since the event $K(i,\epsilon^{\prime})$ is
measurable with regard to $\tilde{\mathcal{V}}_{i}$. The same proofs of Lemmas
$7$, $8$, $9$, $10$ and $33$ from Safsafi (2020) also yields similar results
if we replace the $v(j)$’s with $\tilde{v}(j)$’s. We prove one of those
results as an example here, and direct the reader to Safsafi (2020) for the
rest of the proofs. Let
$t=\frac{2(1+\epsilon^{\prime}/2)f(i)\ell_{n}^{2/3}}{C}$.

######  Lemma 14.

For any $n-t\geq l>0$, we have:

$\mathbb{P}\left(\mathbbm{1}(K(i,\epsilon^{\prime}))\sum_{k=1}^{l}w_{\tilde{v}(k)}\geq
2l^{1/2}\ell_{n}^{1/2}\right)\leq\exp\left({\frac{-l^{1/2}n^{1/6}}{4}}\right).$

###### Proof.

Let $\tilde{J}(1),..,\tilde{J}(l)$ be i.i.d. copies of $\tilde{v}(1)$
conditionnally on $K(i,\epsilon^{\prime})$. Recall that, by Conditions 1,
$\max_{i\leq n}(w_{i})=o(n^{1/3})$. Write $C_{l}=l^{1/2}\ell_{n}^{1/2}$, since
the event $K(i,\epsilon^{\prime})$ is measurable with regard to
$\tilde{\mathcal{V}}_{i}$, we can apply Theorem $1$ in Ben-Hamou, Peres, and
Salez (2018) and Markov’s inequality to obtain:

$\displaystyle\mathbb{P}\left(\sum_{k=1}^{l}w_{\tilde{v}(k)}\geq
2C_{l}\middle|K(i,\epsilon^{\prime})\right)$
$\displaystyle\leq\frac{\mathbb{E}[\exp(\sum_{k=1}^{l}w_{\tilde{v}(k)})|K(i,\epsilon^{\prime})]}{\exp(2C_{l})}$
(3)
$\displaystyle\leq\frac{\mathbb{E}[\exp(\sum_{k=1}^{l}w_{\tilde{J}(i)})]}{\exp(2C_{l})}.$

Moreover:

$\displaystyle\mathbb{E}\left[w_{\tilde{J}(1)}^{2}\right]$
$\displaystyle=\mathbb{E}\left[\left.\sum_{k\not\in\tilde{\mathcal{V}}_{i}}\frac{w_{k}^{3}}{\ell_{n}-\sum_{k^{\prime}\in\tilde{\mathcal{V}}_{i}}w_{k}^{\prime}}\right|K(i,\epsilon^{\prime})\right]$
$\displaystyle=\mathbb{E}\left[\left.\sum_{k\not\in\tilde{\mathcal{V}}_{i}}\frac{w_{k}^{3}}{\ell_{n}}\right|K(i,\epsilon^{\prime})\right](1+o(1))$
$\displaystyle=1-\mathbb{E}\left[\left.\sum_{k\not\in\tilde{\mathcal{V}}_{i}}\frac{w_{k}^{3}}{\ell_{n}}\right|K(i,\epsilon^{\prime})\right](1+o(1))+o(1).$

We have by definition of $K(i,\epsilon^{\prime})$:

$\mathbb{E}\left[\left.\sum_{k\not\in\tilde{\mathcal{V}}_{i}}\frac{w_{k}^{3}}{\ell_{n}}\right|K(i,\epsilon^{\prime})\right]\leq\sum_{k=1}^{t}\frac{w_{k}^{3}}{\ell_{n}}.$

It has already been shown in Safsafi (2020) (proof of Lemma $8$) that
$\sum_{k=1}^{t}\frac{w_{k}^{3}}{\ell_{n}}=o(1).$ Thus:

$\mathbb{E}\left[w_{\tilde{J}(1)}^{2}\right]=1+o(1).$ (4)

And similarly:

$\mathbb{E}\left[w_{\tilde{J}(1)}\right]=1+o(1).$ (5)

By Equations (4), (5) and the Bernstein’s inequality (Bernstein (1924)) for
the $w_{\tilde{J}(i)}$ that stems from the Chernoff bound in Equation (3), we
obtain:

$\displaystyle\mathbb{P}\left(\mathbbm{1}(K(i,\epsilon^{\prime}))\sum_{k=1}^{l}w_{\tilde{v}(k)}\geq
2C_{l}\right)$
$\displaystyle=\mathbb{P}\left(\sum_{k=1}^{l}w_{\tilde{v}(k)}\geq
2C_{l}\middle|K(i,\epsilon^{\prime})\right)\mathbb{P}(K(i,\epsilon^{\prime}))$
(6)
$\displaystyle\leq\exp\left(\frac{-(-l\mathbb{E}[w_{\tilde{J}(1)}]+2C_{l})^{2}}{2(n^{1/3}C_{l}+l\mathbb{E}[w_{\tilde{J}(1)}^{2}])}\right)$
$\displaystyle\leq\exp\left(\frac{-C_{l}^{2}}{4(n^{1/3}C_{l})}\right)$
$\displaystyle\leq\exp\left(\frac{-l^{1/2}n^{1/6}}{4}\right).$

∎

For $n-t\geq l\geq 0$ let
$E_{l}=\\{\sum_{k=1}^{l}w_{\tilde{v}(k)}<2l^{1/2}\ell_{n}^{1/2}\\}$.
Similarly, the following four lemmas are also slight modifications of Lemmas
$8$, $9$, $10$ and $33$ from Safsafi (2020).

######  Lemma 15.

Recall that $C=\frac{\mathbb{E}[W^{3}]}{\mathbb{E}[W]}$. For any $l=o(n)$, and
$l\geq u>1$:

$\mathbb{E}(w_{\tilde{v}(u)}^{2}\mathbbm{1}(K(i,\epsilon^{\prime}))|E_{l})=C+o(1),$

and:

$\mathbb{E}(w_{\tilde{v}(u)}^{2}\mathbbm{1}(K(i,\epsilon^{\prime})))=C+o(1).$

######  Lemma 16.

Let $l=o(n)$. For any integer $l\geq u>0$ we have:

$\mathbb{E}(w_{\tilde{v}(u)}\mathbbm{1}(K(i,\epsilon^{\prime}))|E_{l})=1+o(1).$

######  Lemma 17.

Let $l=o(n)$. For any integer $l\geq u>0$ we have:

$\mathbb{E}(w_{\tilde{v}(l)}w_{\tilde{v}(u)})=1+o(1).$

######  Lemma 18.

Let $u^{\prime}\geq u\geq 0$, then for any $x\geq 0$:

$\mathbb{P}(w_{\tilde{v}(u^{\prime})}\mathbbm{1}(K(i,\epsilon^{\prime}))\geq
x)\leq\mathbb{P}(w_{\tilde{v}(u)}\mathbbm{1}(K(i,\epsilon^{\prime}))\geq x)$

######  Lemma 19.

For any $l=o(n)$ we have :

$\displaystyle\mathbb{E}[w_{\tilde{v}(l)}\mathbbm{1}(K(i,\epsilon^{\prime}))]\leq
1+\frac{l+2(1-\epsilon^{\prime})C^{-1}f(i)\ell_{n}^{2/3}}{\ell_{n}}\left(1-C\right)+o\left(\frac{l+f(i)n^{2/3}}{n}\right).$

###### Proof.

First,. Denote $\\{\tilde{v}(1),\tilde{v}(2),...,\tilde{v}(l)\\}$ by
$\textbf{V}_{l-1}$. Then by definition:

$\displaystyle\mathbb{E}[w_{\tilde{v}(l)}\mathbbm{1}(K(i,\epsilon^{\prime}))]$
$\displaystyle=\mathbb{E}\left[\mathbb{E}[w_{\tilde{v}(l)}\mathbbm{1}(K(i,\epsilon^{\prime}))|(\textbf{V}_{l-1},\tilde{\mathcal{V}}_{i})]\right]$
$\displaystyle=\mathbb{E}\left[\mathbbm{1}(K(i,\epsilon^{\prime}))\sum_{j\not\in\textbf{V}_{l-1}\cup\tilde{\mathcal{V}}_{i}}\frac{w_{j}^{2}}{\ell_{n}-\sum\limits_{j\in\textbf{V}_{l-1}\cup\tilde{\mathcal{V}}_{i}}w_{j}}\right].$

Let

$E_{l}=\left\\{\mathbbm{1}(K(i,\epsilon^{\prime}))\sum_{j\in\textbf{V}_{l-1}\cup\tilde{\mathcal{V}}_{i}}^{l}w_{j}<2l^{1/2}\ell_{n}^{1/2}\right\\},$

then:

$\mathbb{E}[w_{\tilde{v}(l)}\mathbbm{1}(K(i,\epsilon^{\prime}))]=\mathbb{E}\left[w_{\tilde{v}(l)}\mathbbm{1}(K(i,\epsilon^{\prime}))|E_{l}\right]\mathbb{P}\left(E_{l}\right)+\mathbb{E}\left[w_{\tilde{v}(l)}\mathbbm{1}(K(i,\epsilon^{\prime}))|\bar{E}_{l}\right]\mathbb{P}\left(\bar{E}_{l}\right).$
(7)

By Lemma 14, and the fact that $l=o(n)$:

$\displaystyle\mathbb{P}(\bar{E}_{l})$
$\displaystyle\leq\exp\left(\frac{-l^{1/2}n^{1/6}}{4}\right)$
$\displaystyle\leq\exp\left(\frac{-n^{1/6}}{4}\right).$

Hence, by Conditions 1 it follows that:

$\mathbb{E}\left[w_{\tilde{v}(l)}\mathbbm{1}(K(i,\epsilon^{\prime}))|\bar{E}_{l}\right]\mathbb{P}\left(\bar{E}_{l}\right)\leq
n^{1/3}\exp\left(\frac{-n^{1/6}}{4}\right)=o\left(\frac{1}{n}\right),$

together with Equation (7) this yields:

$\displaystyle\mathbb{E}[w_{\tilde{v}(l)}\mathbbm{1}(K(i,\epsilon^{\prime}))]$
$\displaystyle=\mathbb{E}\left[w_{v(l)}|E_{l}\right]\left(1+o\left(\frac{1}{n}\right)\right)+o\left(\frac{1}{n}\right).$
(8)

Moreover, by definition of the event $E_{l}$:

$\displaystyle\mathbb{E}\left[w_{\tilde{v}(l)}\mathbbm{1}(K(i,\epsilon^{\prime}))|E_{l}\right]$
$\displaystyle=\mathbb{E}\left[\mathbbm{1}(K(i,\epsilon^{\prime}))\left.\sum_{j\not\in\textbf{V}_{l-1}\cup\tilde{\mathcal{V}}_{i}}\frac{w_{j}^{2}}{\ell_{n}\left(1-\frac{\sum_{j\in\textbf{V}_{l-1}\cup\tilde{\mathcal{V}}_{i}}w_{j}}{\ell_{n}}\right)}\right|E_{l}\right]$
$\displaystyle=\mathbb{E}\left[\mathbbm{1}(K(i,\epsilon^{\prime}))\left.\sum_{j\not\in\textbf{V}_{l-1}\cup\tilde{\mathcal{V}}_{i}}\frac{w_{j}^{2}}{\ell_{n}}\left(1+\frac{\sum_{j\in\textbf{V}_{l-1}\cup\tilde{\mathcal{V}}_{i}}w_{j}}{\ell_{n}}\right)\right|E_{l}\right]+o\left(\frac{l}{n}\right).$

Let:

$A=\mathbb{E}\left[\frac{\mathbbm{1}(K(i,\epsilon^{\prime}))(\sum_{j\in\textbf{V}_{l-1}\cup\tilde{\mathcal{V}}_{i}}w_{j})(\sum_{i=1}^{n}w_{j}^{2})}{\ell_{n}^{2}}\middle|E_{l}\right],$

and

$B=\mathbb{E}\left[\frac{\mathbbm{1}(K(i,\epsilon^{\prime}))\sum_{j\in\textbf{V}_{l-1}\cup\tilde{\mathcal{V}}_{i}}w_{j}^{2}}{\ell_{n}}\middle|E_{l}\right].$

recall the definition of $t_{1}$ and $t_{2}$ from the chapter before. By
Lemmas 15 and 16, and by definition of $E_{l}$ and
$\mathbbm{1}(K(i,\epsilon^{\prime}))$ and Conditions 1:

$\displaystyle A-B$
$\displaystyle=\mathbb{E}\left[\frac{\mathbbm{1}(K(i,\epsilon^{\prime}))(\sum_{j\in\textbf{V}_{l-1}\cup\tilde{\mathcal{V}}_{i}}(w_{j}-w_{j}^{2}))}{\ell_{n}}\middle|E_{l}\right]+o\left(\frac{n^{2/3}}{n}\right)$
$\displaystyle\leq\mathbb{E}\left[\frac{\sum_{j\in\textbf{V}_{l-1}}(w_{j}-w_{j}^{2})+\sum\limits_{j=t_{1}}^{t_{2}}\left(w_{v(j)}-w_{v(j)}^{2}\right)}{\ell_{n}}\middle|E_{l}\right]+o\left(\frac{n^{2/3}}{n}\right)$
$\displaystyle\leq\frac{l+(t_{2}-t_{1})}{\ell_{n}}\left(1-C\right)+o\left(\frac{n^{2/3}}{n}\right)$
$\displaystyle\leq\frac{l+2(1-\epsilon^{\prime})f(i)\ell_{n}^{2/3}}{\ell_{n}}\left(1-C\right)+o\left(\frac{n^{2/3}}{n}\right).$

It follows that:

$\displaystyle\mathbb{E}\left[w_{\tilde{v}(l)}\mathbbm{1}(K(i,\epsilon^{\prime}))|E_{l}\right]$
$\displaystyle=\mathbb{E}\left[\mathbbm{1}(K(i,\epsilon^{\prime}))\left.\sum_{j\not\in\textbf{V}_{l-1}\cup\tilde{\mathcal{V}}_{i}}\frac{w_{j}^{2}}{\ell_{n}}\left(1+\frac{\sum_{j\in\textbf{V}_{l-1}\cup\tilde{\mathcal{V}}_{i}}w_{j}}{\ell_{n}}\right)\right|E_{l}\right]+o\left(\frac{l}{n}\right)$
$\displaystyle=\frac{\sum_{i=1}^{n}w_{j}^{2}}{\ell_{n}}+A-B$
$\displaystyle-\mathbb{E}\left[\mathbbm{1}(K(i,\epsilon^{\prime}))\frac{\left(\sum_{j\in\textbf{V}_{l-1}\cup\tilde{\mathcal{V}}_{i}}w_{j}^{2}\right)\left(\sum_{j\in\textbf{V}_{l-1}\cup\tilde{\mathcal{V}}_{i}}w_{j}\right)}{\ell_{n}^{2}}\middle|E_{l}\right]+o\left(\frac{l}{n}\right)$
$\displaystyle=\frac{\sum_{i=1}^{n}w_{j}^{2}}{\ell_{n}}+A-B+o\left(\mathbb{E}\left[\mathbbm{1}(K(i,\epsilon^{\prime}))\frac{\sum_{j\in\textbf{V}_{l-1}\cup\tilde{\mathcal{V}}_{i}}w_{j}^{2}}{\ell_{n}}\middle|E_{l}\right]\right)$
$\displaystyle+o\left(\frac{l+f(i)n^{2/3}}{n}\right)$ $\displaystyle\leq
1+\frac{l+2(1-\epsilon^{\prime})f(i)\ell_{n}^{2/3}}{\ell_{n}}\left(1-C\right)+o\left(\frac{l+f(i)n^{2/3}}{n}\right).$

Replacing in Equation (8) finishes the proof. ∎

We draw the attention of the reader to the fact that this proof is very
similar to the one already done in Section $2$ of Safsafi (2020). Since,
conditionally on $\tilde{\mathcal{V}}_{i}$ , the graph
$G(\mathcal{V}\setminus\tilde{\mathcal{V}}_{i},p_{f(i+1)})$ is an
inhomogeneous random graph. This calculation shows that, when
$K(i,\epsilon^{\prime})$ holds, the exploration process of
$G(\mathcal{V}\setminus\tilde{\mathcal{V}}_{i},p_{f(i+1)})$ has slightly
smaller than $1$ increments on expectation. Thus, when
$K(i,\epsilon^{\prime})$ holds,
$G(\mathcal{V}\setminus\tilde{\mathcal{V}}_{i},p_{f(i+1)})$ is slightly
subcritical. In Safsafi (2020), we study extensively the graph
$G(\mathcal{V}\setminus\tilde{\mathcal{V}}_{i},p_{f(i)})$. When the event
$K(i,\epsilon^{\prime})$ holds those two graphs are both slightly subcritical
and have very similar increments distribution. Hence, the upper bound results
that where shown for $G(\mathcal{V}\setminus\tilde{\mathcal{V}}_{i},p_{f(i)})$
can also be shown for
$G(\mathcal{V}\setminus\tilde{\mathcal{V}}_{i},p_{f(i+1)})$ with slightly
larger constants by following the same method of proofs from Safsafi (2020)
under the event $K(i,\epsilon^{\prime})$ and then adding the probability of
$K(i,\epsilon^{\prime})$ not holding. By this argument the following two
theorems are true similarly to their counterparts for the graph
$G(\mathcal{V}\setminus\tilde{\mathcal{V}}_{i},p_{f(i)})$. Theorem 20 is
related to Theorem $3$ from Safsafi (2020), and Theorem 21 is related to
Theorem $4$ from Safsafi (2020). We thus omit their proofs.

######  Theorem 20.

Let $1\geq\epsilon>0$ and $\epsilon^{\prime}>0$ and consider the following
event:
All the connected components of
$G(\mathcal{V}\setminus\tilde{\mathcal{V}}_{i},p_{f(i+1)})$ have size smaller
than

$\frac{\ell_{n}^{2/3}}{Cf(i)^{1-\epsilon}},$

and weight smaller than

$\frac{(1+\epsilon^{\prime})\ell_{n}^{2/3}}{Cf(i)^{1-\epsilon}}.$

There exists a positive constant $A>0$ that only depend on the distribution of
$W$ such that the probability of this event not happening is at most:

$A\left(\exp\left(\frac{-f(i+1)^{\epsilon}}{A}\right)+\exp\left(\frac{-\sqrt{f(i+1)}}{A}\right)+\exp\left(\frac{-n^{1/12}}{A}\right)\right).$

######  Theorem 21.

Let Exc be the maximal excess of the connected components of
$G(\mathcal{V}\setminus\tilde{\mathcal{V}}_{i},p_{f(i+1)})$. There exists a
positive constant $A>0$ such that, for any $1\geq\epsilon>0$ the probability
of

$\textnormal{Exc}\geq Af(i+1)^{\epsilon},$

is at most:

$A\left(\exp\left(\frac{-f(i+1)^{\epsilon/2}}{A}\right)+\exp\left(\frac{-\sqrt{f(i+1)}}{A}\right)+\exp\left(\frac{-n^{1/12}}{A}\right)\right).$

Those theorems deal with the sizes, weights and excesses of the connected
components of $G(\mathcal{V}\setminus\tilde{\mathcal{V}}_{i},p_{f(i+1)})$. In
order to prove bounds on the diameter of those components, we still need to
bound the height of some well-chosen spanning trees and use Lemma 13. This is
why we bound the height of their exploration trees.

###  3.2 Coupling with Galton-Watson trees

In this part, $i\geq 1$ is fixed. The construction described bellow is done
conditionally on $\tilde{\mathcal{V}}_{i}$, the vertices set of the largest
connected component of $G(\textbf{W},p_{f(i)})$.

Let $\tilde{L}$ be the exploration process of
$G(\mathcal{V}\setminus\tilde{\mathcal{V}}_{i},p_{f(i+1)})$. And for $k\geq
1$, let $\tilde{c}(k)$ be the number of children of node $\tilde{v}(k)$ in the
exploration process. If a connected component of
$G(\mathcal{V}\setminus\tilde{\mathcal{V}}_{i},p_{f(i+1)})$ is discovered at
time $k$ then its exploration process will be:

$\tilde{L}^{\prime}_{k}(0)=1.$

And for $i\geq 1$:

$\tilde{L}^{\prime}_{k}(i+1)=\tilde{L}^{\prime}_{k}(i)+\tilde{c}(k+i-1)-1.$

This exploration process stops when it hits $0$. For
$(k,l)\in(\mathcal{V}\setminus\tilde{\mathcal{V}}_{i})^{2}$, let $X(k,l,i+1)$
be a Bernoulli random variable of parameter

$1-\exp(-w_{k}w_{l}p_{f(i+1)}).$

Then for any $k\geq 1$, by definition of the exploration process, if a
connected component is discovered at time $k$ the number of children of node
$\tilde{v}(k)$ has the the same distribution as:

$\sum_{\tilde{v}(l)\in\mathcal{V}\setminus\tilde{\mathcal{V}}_{i},\,l\geq
1+k}X(\tilde{v}(k),\tilde{v}(l),i+1).$

Generally, if node $\tilde{v}(k+i)$ is in the same connected component as
$\tilde{v}(k)$, then the distribution of $\tilde{c}(k+i)$ will be the same as
the distribution of:

$\sum_{l\geq\tilde{L}^{\prime}_{k}(i)+k+i}X(\tilde{v}(k+i),\tilde{v}(l),i+1).$

For each $k\geq 0$, let $\tilde{\mathbb{T}}(k)$ be the tree with exploration
process $\tilde{L}^{\prime}_{k}$. If we can bound the height of
$\tilde{\mathbb{T}}(k)$ for every $k\geq 1$, then we will have a bound on the
height of the largest exploration tree in
$G(\mathcal{V}\setminus\tilde{\mathcal{V}}_{i},p_{f(i+1)})$. In order to do
so, we create a Galton-Watson tree $\mathbb{T}(k)$ that contains a sub-tree
with the same distribution as $\tilde{\mathbb{T}}(k)$ in the following way:

Conditionally on
$\textbf{V}_{k-1}=(\tilde{v}(1),\tilde{v}(2),...,\tilde{v}(k-1))$ and
$\tilde{\mathcal{V}}_{i}$, we construct a Galton-Watson tree $\mathbb{T}(k)$.
Start by one node, and for each new node created follow these two steps. First
give the node a label which is a random variable with the distribution of
$\tilde{v}(k)$ independently of everything else. And then conditionally on the
node label being $r$ give it a random number of children which is a Poisson
random variable of parameter:

$w_{r}\left(\ell_{n}-\sum_{l\in\textbf{V}_{k-1}\cup\tilde{\mathcal{V}}_{i}}w_{l}\right)p_{f(i+1)},$

independently of everything else 333Here we abused notations by using the
$\textbf{V}_{k-1}$ as a set and as a sequence at the same time. It remains
clear from the context which concept we are using.. Remark that this process
may not end, in that case we get an infinite tree. $\mathbb{T}(k)$ is thus a
Galton-Watson tree with reproduction distribution $\mu(k,i+1)$, which is,
conditionally on $(\textbf{V}_{k},\tilde{\mathcal{V}}_{i})$, a Poisson
distribution of parameter

$w_{\tilde{v}(k)}\left(\ell_{n}-\sum_{l\in\textbf{V}_{k-1}\cup\tilde{\mathcal{V}}_{i}}w_{l}\right)p_{f(i+1)}.$

In order to have a clear order on the nodes of $\mathbb{T}(k)$, we sort them
in a breadth-first search fashion while creating the tree. We start from one
node, which is the root of $\mathbb{T}(k)$. We give it order $1$, label
$r(1)$. The root then has $b(1)$ children with the distributions described
above. The children of the root are given orders in $(2,3...,b(1)+1)$ randomly
uniformly. Now do same for the the node with order $2$ and order its children
$(b(1)+2,b(1)+2,...,b(1)+b(2)+1)$ randomly uniformly too. Continue in this
fashion until there are no new nodes or the construction never ends. We call
this the breadth-first order of $\mathbb{T}(k)$ .

We construct a subtree $\mathbb{T}^{\prime}(k)$ by pruning $\mathbb{T}(k)$
with the following algorithm. $\mathbb{L}$ is the list of nodes currently
investigated by the algorithm. Initially $\mathbb{L}$ contains just the root :

  1. 1.

At step $1$ color the root in red, then add the children of the root to
$\mathbb{L}$.

  2. 2.

At step $i$ consider the $i$-th node added to $\mathbb{L}$ following the
breadth-first order. If there are no other red nodes with the same label yet,
then color it in red and add its childer to $\mathbb{L}$.

  3. 3.

Continue like this as long as $\mathbb{L}$ is not empty.

Figure 6: An example of the colouring procedure. The breath-first order is
implicitly induced by the drawing, nodes are ordered from bottom to top and
from left to right. Each node has its label directly to its right. We only
show the steps where a whole generation has been considered.

Since there is only a finite number of labels, this process will eventually
end. The nodes are always removed from $\mathbb{L}$ following the breadth-
first order. After finishing this procedure, we obtain a subtree of
$\mathbb{T}(k)$ composed only of red nodes that we denote by
$\mathbb{T}^{\prime}(k)$. This fact is easily seen from the procedure since a
node can only be red if its parent is also red. Moreover, we have the
following lemma. This result was already shown in Norros and Reittu (2006)
(proposition $3.1$) and proven again in Bhamidi et al. (2010) for
$\mathbb{T}^{\prime}(1)$. The proof for general $\mathbb{T}^{\prime}(k)$ is
the same conditionally on $\textbf{V}_{k-1}$, and so we refer to those
articles for a proof.

######  Lemma 22.

For $k\geq 1$, conditionally on
$(\tilde{v}(1),\tilde{v}(2),...,\tilde{v}(k-1))$, the tree
$\mathbb{T}^{\prime}(k)$ has the same distribution as $\tilde{\mathbb{T}}(k)$.

By Lemma 22, in order to bound the heights of the exploration trees of
$G(\mathcal{V}\setminus\tilde{\mathcal{V}}_{i},p_{f(i+1)})$ it is sufficient
to bound the heights of the trees $\mathbb{T}^{\prime}(k)$ for $k\geq 1$.
Since the $\mathbb{T}^{\prime}(k)$’s are substrees of the $\mathbb{T}(k)$’s,
we will bound the heights of the later. The following lemma revolves around
classical results on Galton-Watson trees.

######  Lemma 23.

For $k\geq 1$. Let $H(\mathbb{T}(k))$ be the height of tree $\mathbb{T}(k)$.
For $m\geq 0$, denote the event $\left\\{H(\mathbb{T}(k))\geq m\right\\}\cap
K(i,1/8)$ by $\textbf{Q}(k,m)$. If $k\leq\ell_{n}^{6/7}$ then:

$\mathbb{P}\left(\textbf{Q}\left(k,\frac{2\ell_{n}^{1/3}}{\sqrt{f(i+1)}}\right)\right)\leq\frac{A\sqrt{f(i+1)}}{{\ell_{n}^{1/3}}}\exp\left(\frac{-Ck}{2\sqrt{f(i+1)}\ell_{n}^{2/3}}-\frac{\sqrt{f(i+1)}}{8}\right).$

And if $k\geq\ell_{n}^{6/7}$ then:

$\displaystyle\mathbb{P}\left(\textbf{Q}\left(k,\frac{2\ell_{n}^{1/3}}{\sqrt{f(i+1)}}\right)\right)\leq\frac{A\sqrt{f(i+1)}}{{\ell_{n}^{1/3}}}\exp\left(\frac{-C\ell_{n}^{6/7}}{2\sqrt{f(i+1)}\ell_{n}^{2/3}}-\frac{\sqrt{f(i+1)}}{8}\right).$

###### Proof.

For simplicity and without loss of generality suppose that $m$ is even.
Clearly:

$\displaystyle\mathbb{P}(\textbf{Q}(k,m))$
$\displaystyle\leq\mathbb{E}[\mu(k,i+1)\mathbbm{1}(K(i,1/8))]\mathbb{P}(\textbf{Q}(k,m-1)))$
(9)
$\displaystyle\leq\mathbb{E}[\mu(k,i+1)\mathbbm{1}(K(i,1/8))]^{m/2}\mathbb{P}(\textbf{Q}(k,m/2))$

Moreover, $\mathbbm{1}(K(i,1/8))$ is measurable with regard to
$\tilde{\mathcal{V}}_{i}$ by definition. This remark and Lemma 17 alongside
the fact that for $x\in\mathbb{R}$, $1-e^{-x}\leq x$ yield:

$\displaystyle\mathbb{E}[\mu(v(k),i+1)\mathbbm{1}(K(i,1/8))]$
$\displaystyle=\mathbb{E}\left[\mathbb{E}\left[\mu(v(k),i+1)\mathbbm{1}(K(i,1/8))\middle|\tilde{\mathcal{V}}_{i},\textbf{V}_{k}\right]\right]$
$\displaystyle\leq\mathbb{E}\left[w_{\tilde{v}(k)}\left(\ell_{n}-\sum_{l\in\textbf{V}_{k-1}\cup\tilde{\mathcal{V}}_{i}}w_{l}\right)p_{f(i+1)}\mathbbm{1}(K(i,1/8))\right]$
$\displaystyle\leq\mathbb{E}\left[w_{\tilde{v}(k)}\left(\ell_{n}-\frac{7f(i)\ell_{n}^{2/3}}{4C}\right)p_{f(i+1)}\mathbbm{1}(K(i,1/8))\right]-\frac{k}{\ell_{n}}(1+o(1)).$

Hence, by Lemma 19, a quick calculation yields for $k\leq\ell_{n}^{6/7}$:

$\displaystyle\mathbb{E}[\mu(k,i+1)\mathbbm{1}(K(i,1/8))]$ (10)
$\displaystyle\leq\left(1+\frac{k+\frac{7}{4C}f(i)\ell_{n}^{2/3}}{\ell_{n}}\left(1-C\right)\right)\left(1+\frac{f(i+1)}{\ell_{n}^{1/3}}-\frac{7f(i)}{4C\ell_{n}^{1/3}}\right)-\frac{k}{\ell_{n}}+o\left(\frac{k+f(i)n^{2/3}}{n}\right)$
$\displaystyle\leq
1-\frac{Ck}{\ell_{n}}-\frac{f(i)}{4\ell_{n}^{1/3}}+o\left(\frac{k+f(i)n^{2/3}}{n}\right)$

It is also well known, for critical Galton-Watson trees (see for example Lemma
$6.7$ of Bhamidi, van der Hofstad, and Sen (2018)), that there exists a
constant $A>0$ such that for any $m\geq 0$:

$\mathbb{P}(\textbf{Q}(k,m/2))\leq\frac{A}{m},$ (11)

this result is thus also true for a subcritical Galton-Watson tree.

Hence, by Equation (9), (LABEL:eqf12), and (11), a simple computation yields:

$\displaystyle\mathbb{P}\left(\textbf{Q}\left(k,\frac{2\ell_{n}^{1/3}}{\sqrt{f(i+1)}}\right)\right)\leq\frac{A\sqrt{f(i+1)}}{{\ell_{n}^{1/3}}}\mathbb{E}[\mu(k,i+1)\mathbbm{1}(K(i,1/8))]^{\frac{\ell_{n}^{1/3}}{\sqrt{f(i+1)}}}$
(12)
$\displaystyle=\frac{A\sqrt{f(i+1)}}{{\ell_{n}^{1/3}}}\exp\left(\frac{-Ck}{\sqrt{f(i+1)}\ell_{n}^{2/3}}-\frac{\sqrt{f(i+1)}}{4}+o\left(\frac{k+f(i)n^{2/3}}{\sqrt{f(i+1)}n^{2/3}}\right)\right)$
$\displaystyle\leq\frac{A\sqrt{f(i+1)}}{{\ell_{n}^{1/3}}}\exp\left(\frac{-Ck}{2\sqrt{f(i+1)}\ell_{n}^{2/3}}-\frac{\sqrt{f(i+1)}}{8}\right)$

Moreover, for $k\geq\ell_{n}^{6/7}$, by Lemma 18:

$\mathbb{E}[w_{\tilde{v}(k)}\mathbbm{1}(K(i,1/8))]\leq\mathbb{E}\left[w_{\tilde{v}\left(\ell_{n}^{6/7}\right)}\mathbbm{1}(K(i,4))\right].$

With this fact and Equations (LABEL:eq14), we get for $k\geq\ell_{n}^{6/7}$:

$\displaystyle\mathbb{P}\left(\textbf{Q}\left(k,\frac{2\ell_{n}^{1/3}}{\sqrt{f(i+1)}},\right)\geq\frac{2\ell_{n}^{1/3}}{\sqrt{f(i+1)}}\right)\leq\frac{A\sqrt{f(i+1)}}{{\ell_{n}^{1/3}}}\exp\left(\frac{-C\ell_{n}^{6/7}}{2\sqrt{f(i+1)}\ell_{n}^{2/3}}-\frac{\sqrt{f(i+1)}}{8}\right)$

∎

In order to bound the height of all the exploration trees at once, we need a
bound on the number of connected components in
$G(\mathcal{V}\setminus\tilde{\mathcal{V}}_{i},p_{f(i+1)})$. The order of
nodes in the exploration process of
$G(\mathcal{V}\setminus\tilde{\mathcal{V}}_{i},p_{f(i+1)})$ has the same
distribution as that of
$G(\mathcal{V}\setminus\tilde{\mathcal{V}}_{i},p_{f(i)})$. Moreover
conditionally on that order, the exploration process of
$G(\mathcal{V}\setminus\tilde{\mathcal{V}}_{i},p_{f(i)})$ is stochastically
upper bounded by the exploration process of
$G(\mathcal{V}\setminus\tilde{\mathcal{V}}_{i},p_{f(i+1)})$. Since, by
definiton, the number of connected components discovered in an interval of
time of the BFW correspond to the number of new minimums attained in that same
interval. It is clear by this argument that for any $m\in\mathbb{N}$ and
$(t_{1},t_{2})\in\mathbb{N}^{2}$ such that $t_{1}\leq t_{2}$, the probability
of discovering more than $m$ connected components in the BFW of
$G(\mathcal{V}\setminus\tilde{\mathcal{V}}_{i},p_{f(i+1)})$ between times
$t_{1}$ and $t_{2}$ is smaller than the probability of discovering more than
$m$ connected components in the BFW of
$G(\mathcal{V}\setminus\tilde{\mathcal{V}}_{i},p_{f(i)})$.

######  Lemma 24.

Let $r_{1}=\frac{\ell_{n}^{2/3}}{\sqrt{f}C}$. Let $D_{0}$ be the event "The
number of connected component discovered before time $r_{1}$ in the
exploration process of
$G(\mathcal{V}\setminus\tilde{\mathcal{V}}_{i},p_{f(i+1)})$ is larger than
$\frac{\sqrt{f(i)}\ell_{n}^{1/3}}{2C}$."

For $j\geq 1$, consider the interval

$I_{j}=\left[r_{1}+\frac{(j^{2}-1)f(i+1)\ell_{n}^{2/3}}{C},r_{1}+\frac{((j+1)^{2}-1)f(i+1)\ell_{n}^{2/3}}{C}\right)$

and let $\tilde{j}$ be the greatest integer such that:

$\frac{(\tilde{j}^{2}-1)f(i+1)\ell_{n}^{2/3}}{C}\leq\ell_{n}^{6/7}.$

For some $\tilde{j}\geq j\geq 1$, let $D_{j}$ be the event "There are more
than $j^{3}f(i)\ell_{n}^{1/3}$ connected components discovered in the interval
$I_{j}$ in the exploration process of
$G(\mathcal{V}\setminus\tilde{\mathcal{V}}_{i},p_{f(i+1)})$."

There exists a constant $A>0$ such that:

$\mathbb{P}\left(\bigcup_{j=0}^{\tilde{j}}(D_{j})\right)\leq
A\exp\left(\frac{-\sqrt{f}}{A}\right)+A\exp\left(\frac{-n^{1/12}}{A}\right).$

###### Proof.

By the arguments given before, it is sufficient to show this result for the
exploration process of
$G(\mathcal{V}\setminus\tilde{\mathcal{V}}_{i},p_{f(i)})$. Recall that the
exploration process can only go down by $1$, so the number of connected
components discovered in an interval of time is equal the number of times a
new minimum was attained by the exploration process in that same interval of
time. Hence, by Equation $75$ in Safsafi (2020), the probability of
discovering more than $\frac{\sqrt{f}\ell_{n}^{1/3}}{2C}$ connected components
before time $r_{1}$ in the exploration process of
$G(\mathcal{V}\setminus\tilde{\mathcal{V}}_{i},p_{f(i)})$ is at most:

$A\exp\left(\frac{-\sqrt{f}}{A}\right).$ (13)

And by using the union bound between Theorem $26$ and Corollary $36.2$ in
Safsafi (2020) we obtain:

$\mathbb{P}\left(\bigcup_{j=1}^{\tilde{j}}(D_{j})\right)\leq
A\exp\left(\frac{-\sqrt{f}}{A}\right)+A\exp\left(\frac{-n^{1/12}}{A}\right).$
(14)

∎

With Lemmas 23 and 24 we get bounds on the height of the exploration trees of
$G(\mathcal{V}\setminus\tilde{\mathcal{V}}_{i},p_{f(i+1)})$. On the other
hand, Theorem 21 gives bounds on its excess. With this in hand, the following
theorem combines those results in order to give an upper bound for the
diameter of $G(\mathcal{V}\setminus\tilde{\mathcal{V}}_{i},p_{f(i+1)})$.

######  Theorem 25.

There exists a constant $A>0$ such that:

$\mathbb{P}\left(\textnormal{diam}(G(\mathcal{V}\setminus\tilde{\mathcal{V}}_{i},p_{f(i+1)}))\geq\frac{A\ell_{n}^{1/3}}{f(i+1)^{1/4}}\right)\leq
A\left(\exp\left(\frac{-f(i+1)^{1/8}}{A}\right)\right).$

###### Proof.

By Equation (2), there exists a constant $A>0$ such that, the probability of
the event $K\left(i,1/8\right)$ not holding is at most:

$A\exp\left(\frac{-f(i)}{A}\right).$ (15)

When that event holds, it is to sufficient study the event
$\textbf{Q}\left(k,\frac{2\ell_{n}^{1/3}}{\sqrt{f(i+1)}}\right)$ and bound the
surplus and then use the union bound. Recall the definition of the events
$(D_{j})_{j\leq\tilde{j}}$ and the intervals $(I_{j})_{j\leq\tilde{j}}$ from
Lemma 24. If all those events are verified, then by the union bound, in each
interval $I_{j}$, the probability that there exists an exploration tree with
height larger than $\frac{2\ell_{n}^{1/3}}{\sqrt{f(i+1)}}$ is at most:

$B_{j}=j^{3}f(i)\ell_{n}^{1/3}\frac{A\sqrt{f(i+1)}}{{\ell_{n}^{1/3}}}\exp\left(\frac{-C(j^{2}-1)f(i+1)\ell_{n}^{2/3}}{2C\sqrt{f(i+1)}\ell_{n}^{2/3}}-\frac{\sqrt{f(i+1)}}{8}\right).$

Recall that $r_{1}=\frac{\ell_{n}^{2/3}}{\sqrt{f}C}$. The probability that
there exists an exploration tree with height larger than
$\frac{2\ell_{n}^{1/3}}{\sqrt{f(i+1)}}$ before time $r_{1}$ is at most:

$B_{0}=\frac{\sqrt{f(i)}\ell_{n}^{1/3}}{2C}\frac{A\sqrt{f(i+1)}}{{\ell_{n}^{1/3}}}\exp\left(-\frac{\sqrt{f(i+1)}}{8}\right).$

Hence, for it to be an exploration tree with height larger than
$\frac{2\ell_{n}^{1/3}}{\sqrt{f(i+1)}}$, either one of the events
$(D_{j})_{0\leq j\leq\tilde{j}}$ does not hold or $K\left(i,1/8\right)$ does
not hold, or one of the event
$\textbf{Q}\left(k,\frac{2\ell_{n}^{1/3}}{\sqrt{f(i+1)}}\right)$ does not hold
or there is a connected component discovered after time $\ell_{n}^{6/7}$ with
an exploration tree with height larger than
$\frac{2\ell_{n}^{1/3}}{\sqrt{f(i+1)}}$. There are less than $n$ connected
component discovered after time $\ell_{n}^{6/7}$. Hence, by Equation (15) and
Lemmas 23 and 24, there exists constants $A>0$ and $A^{\prime}>0$ such that,
the probability that there exists a connected component with an exploration
tree of height larger than $\frac{2\ell_{n}^{1/3}}{\sqrt{f(i+1)}}$ is at most:

$\displaystyle
A\exp\left(\frac{-f(i)}{A}\right)+\sum_{j=0}^{\tilde{j}}B_{j}+n\frac{A\sqrt{f(i+1)}}{{\ell_{n}^{1/3}}}\exp\left(\frac{-C\ell_{n}^{6/7}}{2\sqrt{f(i+1)}\ell_{n}^{2/3}}-\frac{\sqrt{f(i+1)}}{8}\right)+\mathbb{P}\left(\bigcup_{j=1}^{\tilde{j}}(D_{j})\right)$
(16) $\displaystyle\leq
A^{\prime}\exp\left(\frac{-\sqrt{f(i)}}{A^{\prime}}\right)+A^{\prime}\exp\left(\frac{-n^{1/12}}{A^{\prime}}\right).$

Recall that Exc is the maximal excess of the connected components of
$G(\mathcal{V}\setminus\tilde{\mathcal{V}}_{i},p_{f(i+1)})$. By Theorem 21,
there exists a positive constant $A^{\prime\prime}>0$ such that, for any
$1>\epsilon>0$:

$\displaystyle\mathbb{P}\left(\textnormal{Exc}\geq
A^{\prime\prime}f(i+1)^{\epsilon}\right)\leq$ $\displaystyle
A^{\prime\prime}\left(\exp\left(\frac{-f(i+1)^{\epsilon/2}}{A^{\prime\prime}}\right)+\exp\left(\frac{-\sqrt{f(i+1)}}{A^{\prime\prime}}\right)+\exp\left(\frac{-n^{1/12}}{A^{\prime\prime}}\right)\right).$
(17)

Taking $\epsilon=1/4$ in Equation (17) and using Lemma 13 with Equations
(LABEL:eqf142) and (17) then yields:

$\displaystyle\mathbb{P}\left(\textnormal{diam}(G(\mathcal{V}\setminus\tilde{\mathcal{V}}_{i},p_{f(i+1)}))\geq\frac{A\ell_{n}^{1/3}}{f(i+1)^{1/4}}\right)$
$\displaystyle\leq
A\left(\exp\left(\frac{-f(i+1)^{1/8}}{A}\right)+\exp\left(\frac{-n^{1/12}}{A}\right)\right)$
$\displaystyle\leq
A^{\prime}\left(\exp\left(\frac{-f(i+1)^{1/8}}{A^{\prime}}\right)\right).$

∎

##  4 Bounding the diameter of the giant component

###  4.1 A new pruning procedure for the giant component

Take $f\geq f(0)$, we consider the exploration process until time
$t=\frac{5f\ell_{n}^{2/3}}{2C}$. We know by Theorem 12 that the giant
component is fully discovered before $t$ with some high probability. In order
to bound the diameter of the giant component, a natural idea would be to
couple the trees discovered before times $t$ with a sequence of i.i.d. Galton-
Watson trees with the distribution of $\tilde{\mathbb{T}}(1)$ by using the
same colouring of the nodes described in Sub-section 3.2. However,
$\tilde{\mathbb{T}}(1)$ is slightly supercritical. Thus, some of the Galton-
Watson trees we couple with will have infinite size. To solve this problem we
first add i.i.d. cuts with probability $\frac{2f}{\ell_{n}^{1/3}}$ to the
edges of $G(\textbf{W},p_{f(i)})$. Then we couple the new smaller exploration
trees obtained with i.i.d. Galton-Watson trees with the the distribution of:

$\sum_{l=1}^{n}\tilde{X}(v(1),l,i),$

where $\tilde{X}(k,l,i)$ is the product of two i.i.d. Bernoulli random
variables. The first one corresponds to "having an edge" and has parameter:

$\left(1-\exp(-w_{k}w_{l}p_{f(i+1)})\right),$

the second one corresponds to "not having a cut" and has parameter:

$\left(1-\frac{2f}{\ell_{n}^{1/3}}\right).$

We then apply the procedure of Sub-section 3.2 on those Galton-Watson trees.
This yields a new two steps procedure, first pruning then coloring, which
gives a forest of i.i.d. slightly sub-critical Galton-Watson trees. Moreover,
the sum of heights of those Galton-Watson trees is an upper bound of the
height of any exploration tree discovered before time $t$.

We start by bounding the number of Galton-Watson trees obtained by this
construction. A new tree is created at each cut. This means that the total
number of Galton-Watson trees after pruning is equal to the number of cuts
plus the number of initial trees. However, if we are only interested in the
height of one tree. Only the number of cuts is of interest. Hence, even though
we have a bound on the initial number of trees before time $t$ by Safsafi
(2020). We, in fact only need a bound on the number of cuts. This is given in
the following lemma.

######  Lemma 26.

The number of cuts in the pruning procedure is less than
$\frac{6f^{2}\ell_{n}^{1/3}}{C}$ with probability at least:

$1-\exp\left(-2Cf^{3}\right).$

###### Proof.

Because a tree of size $m$ has $m-1$ edges, there are less than $t$ edges in
the exploration trees before time $t$. Let $J$ be the number of edge cuts,
then:

$\mathbb{E}[J]\leq\frac{5f^{2}\ell_{n}^{1/3}}{C}.$

Hence, by Hoeffding’s inequality:

$\displaystyle\mathbb{P}\left(J\geq\frac{6f^{2}\ell_{n}^{1/3}}{C}\right)$
$\displaystyle\leq\exp\left(\frac{-2(f^{2}\ell_{n}^{1/3})^{2}}{t}\right)$
$\displaystyle\leq\exp\left(\frac{-4Cf^{3}}{5}\right).$

∎

Since $C=\frac{\mathbb{E}[W^{3}]}{\mathbb{E}[W]}\geq 1$, this lemma shows that
w.h.p the number of Galton-Watson trees obtained by the pruning then coupling
procedure is less than $6f^{2}\ell_{n}^{1/3}+1\leq 7f^{2}\ell_{n}^{1/3}$.

###  4.2 Bounding the diameter

With this in hand, we can prove a bound on the height of the exploration tree
of the largest component. We denote the Galton-Watson trees constructed by
pruning by $(\mathbb{T}^{\top}(k))_{k\geq 1}$. We use a simple union bound.
Either there is some tree discovered before time $t$ with large height, or the
largest connected component is discovered after time $t$. We already have a
bound on the latter event, and we bound the former event to get the following
theorem. Bounding the height of an exploration tree discovered before time $t$
by the sum of heights of all the $(\mathbb{T}^{\top}(k))_{k\geq 1}$’s will not
yield a good enough upper bound. But this first step will allow us to use a
recursive argument which yields the tight bound presented here.

######  Theorem 27.

There exist constants $A^{\prime}>0$ and $A>0$ such that the exploration tree
of the largest component of $G(\textbf{W},p_{f})$, denoted by
$H(\textbf{W},p_{f})$, has height smaller than $A^{\prime}f^{2}\ell_{n}^{1/3}$
with probability at least:

$1-A\exp\left(\frac{-f}{A}\right).$

###### Proof.

Let $\mathcal{B}_{1}$ be the event: the exploration of the largest component
of $G(\textbf{W},p_{f})$ is not already done at time $t$. By Theorem $1$ in
Safsafi (2020):

$\mathbb{P}(\mathcal{B}_{1})\leq A\exp\left(\frac{-f}{A}\right),$ (18)

with $A>0$ a large constant.

Let $R$ be the random number of cuts obtained after pruning the exploration
trees up to time $t$. And let $\mathcal{B}_{2}$ be the event: $R$ is larger
than $7f^{2}\ell_{n}^{1/3}$. By Lemma 26:

$\mathbb{P}(\mathcal{B}_{2})\leq A\exp\left(\frac{-f^{3}}{A}\right).$ (19)

If the largest component is discovered before time $t$, the height of its
exploration tree $\text{ht}(H(\textbf{W},p_{f}))$ will be smaller than the sum
of heights of all the trees obtained after pruning. By exactly the same method
we used in the proof of Lemma 23, there exists $A>0$ such that for any $r>0$:

$\mathbb{P}(\text{ht}(\mathbb{T}^{\top}(1)))\geq
r)\leq\frac{A}{r}\exp\left(\frac{-fr}{2\ell_{n}^{1/3}}\right),$ (20)

and by the union bound:

$\mathbb{P}\left(\sup_{k\leq
7f^{2}\ell_{n}^{1/3}}\text{ht}(\mathbb{T}^{\top}(k)))\geq\ell_{n}^{1/3}\right)\leq
A^{\prime}\exp\left(\frac{-f}{A^{\prime}}\right),$ (21)

with $A^{\prime}>0$ a large constant. Denote the event

$\left\\{\sup_{k\leq
7f^{2}\ell_{n}^{1/3}}\text{ht}(\mathbb{T}^{\top}(k)))\geq\ell_{n}^{1/3}\right\\}$

by $\mathcal{B}_{3}$. Using Equations (18) and (19) alongside Equation (21)
shows that:

$\mathbb{P}(\mathcal{B}_{1}\cup\mathcal{B}_{2}\cup\mathcal{B}_{3})\leq
A\exp\left(\frac{-f}{A}\right).$ (22)

Let
$\tilde{\mathcal{B}}=\bar{\mathcal{B}}_{1}\cap\bar{\mathcal{B}}_{2}\cap\bar{\mathcal{B}}_{3}$.
If $\tilde{\mathcal{B}}$ holds, then the height of the exploration tree of the
largest component is smaller than the sum of heights of the trees
$((\mathbb{T}^{\top}(k))_{k\leq 7f^{2}\ell_{n}^{1/3}}$. By a small
computation, since $f=o(n^{1/3})$, we have by Equation (20):

$\displaystyle\mathbb{E}[\textnormal{ht}(\mathbb{T}^{\top}(1))]$
$\displaystyle=\sum_{r=0}^{\infty}\mathbb{P}(\textnormal{ht}(\mathbb{T}^{\top}(1))\geq
r)$ (23) $\displaystyle\leq
1+\sum_{r=1}^{\infty}\frac{A}{r}\exp\left(\frac{-fr}{2\ell_{n}^{1/3}}\right)$
$\displaystyle\leq
1+\sum_{r=1}^{\frac{\ell_{n}^{1/3}}{f}}\frac{A}{r}+\sum_{r=\frac{\ell_{n}^{1/3}}{f}+1}^{\infty}\frac{Af}{\ell_{n}^{1/3}}\exp\left(\frac{-fr}{2\ell_{n}^{1/3}}\right)$
$\displaystyle\leq
A^{\prime}\log\left(\frac{\ell_{n}^{1/3}}{f}\right)+\frac{A^{\prime}f}{\ell_{n}^{1/3}\left(1-\exp\left(\frac{-f}{2\ell_{n}^{1/3}}\right)\right)}$
$\displaystyle=O\left(\log\left(\frac{n^{1/3}}{f}\right)\right)$

and similarily

$\displaystyle\mathbb{E}[\textnormal{ht}(\mathbb{T}^{\top}(1))^{2}]$
$\displaystyle=\sum_{r=0}^{\infty}r^{2}\mathbb{P}(\textnormal{ht}(\mathbb{T}^{\top}(1))=r)$
(24)
$\displaystyle\leq\sum_{r=0}^{\infty}r(r+1)\mathbb{P}(\textnormal{ht}(\mathbb{T}^{\top}(1))=r)$
$\displaystyle=\sum_{r=0}^{\infty}2\mathbb{P}(\textnormal{ht}(\mathbb{T}^{\top}(1))=r)\left(\sum_{j=0}^{r}j\right)$
$\displaystyle=2\sum_{j=0}^{\infty}j\left(\sum_{r=j}^{\infty}\mathbb{P}(\textnormal{ht}(\mathbb{T}^{\top}(1))=r)\right)$
$\displaystyle=2\sum_{j=0}^{\infty}j\mathbb{P}(\textnormal{ht}(\mathbb{T}^{\top}(1))\geq
j)$ $\displaystyle=O\left(\frac{n^{1/3}}{f}\right).$

Hence, by Bernstein’s inequality (Bernstein (1924)) for $A^{\prime}>0$ large
enough, there exists a large constant $A>0$ such that:

$\displaystyle\mathbb{P}\left(\sum_{k=1}^{R}\text{ht}(\mathbb{T}^{\top}(k))\mathbbm{1}(\tilde{\mathcal{B}})\geq
A^{\prime}f^{2}\ell_{n}^{1/3}\log\left(\frac{n^{1/3}}{f}\right)\right)$ (25)
$\displaystyle\leq\mathbb{P}\left(\sum_{k=1}^{7f^{2}\ell_{n}^{1/3}}\text{ht}(\mathbb{T}^{\top}(k)))\mathbbm{1}(\text{ht}(\mathbb{T}^{\top}(k))\leq\ell_{n}^{1/3})\geq
A^{\prime}f^{2}\ell_{n}^{1/3}\log\left(\frac{n^{1/3}}{f}\right)\right)$
$\displaystyle\leq
A\exp\left(\frac{-\log\left(\frac{n^{1/3}}{f}\right)f^{2}}{A}\right).$

Suppose now that the height of the exploration tree of any connected component
discovered before time $t$ is at most
$A^{\prime}f^{2}\ell_{n}^{1/3}\log\left(\frac{n^{1/3}}{f}\right)$, with
$A^{\prime}$ the constant of Equation (LABEL:eql17). Denote that event by
$\mathcal{S}$. In that case, the number of cuts (denoted by $\mathcal{P}$) in
one of the longuest paths in the exploration tree of $H(\textbf{W},p_{f})$
verifies by Bernstein’s inequality (Bernstein (1924)):

$\mathbb{P}\left(\mathcal{P}\mathbbm{1}(\mathcal{S})\geq
5A^{\prime}f^{3}\log\left(\frac{n^{1/3}}{f}\right)\right)\leq
A^{\prime\prime}\exp\left(\frac{-\log\left(\frac{n^{1/3}}{f}\right)f^{2}}{A^{\prime\prime}}\right),$
(26)

We have for $n$ large enough, for any $7f^{2}\ell_{n}^{1/3}\geq u\geq 1$:

$\binom{7f^{2}\ell_{n}^{1/3}}{u}\leq\frac{(7f^{2}\ell_{n}^{1/3})^{u}}{u!}\leq\left(\frac{7f^{2}\ell_{n}^{1/3}e}{u}\right)^{u}$

With this we can bound the height of the $u$’th highest tree, denoted by
$\mathbb{T}^{\top}_{u}$. By Equation (20) there exist some large constants
$A>0$ and $A^{\prime}>0$ such that:

$\displaystyle\mathbb{P}\left(\text{ht}(\mathbb{T}^{\top}_{u})\mathbbm{1}(\tilde{\mathcal{B}})\geq\frac{\ell_{n}^{1/3}}{\sqrt{u}}\right)$
$\displaystyle\leq\left(\frac{A\sqrt{u}}{\ell_{n}^{1/3}}\exp\left(\frac{-f}{2\sqrt{u}}\right)\right)^{u}\binom{7f^{2}\ell_{n}^{1/3}}{u}$
(27)
$\displaystyle\leq\left(\frac{A\sqrt{u}}{\ell_{n}^{1/3}}\exp\left(\frac{-f}{2\sqrt{u}}\right)\right)^{u}\left(\frac{7ef^{2}\ell_{n}^{1/3}}{u}\right)^{u}$
$\displaystyle\leq\left(\frac{7Aef^{2}}{\sqrt{u}}\exp\left(\frac{-f}{2\sqrt{u}}\right)\right)^{u}$
$\displaystyle\leq
A^{\prime}\exp\left(\frac{-\sqrt{u}f-u\log{\left(\frac{u}{f}\right)}}{A^{\prime}}\right).$

Let $m=5A^{\prime}f^{3}\log\left(\frac{n^{1/3}}{f}\right)$. If
$\mathcal{P}\leq m$, then the height of the largest component is smaller than
the sum of heights of the $m$ highest Galton-Watson trees
$(\mathbb{T}^{\top}_{u})_{u\leq m}$. By the union bound, using Equations
(22),(LABEL:eql17), (26), and (27), there exist $A>0$ and $A^{\prime}>0$ large
enough such that:

$\displaystyle\mathbb{P}\left(\sum_{u=1}^{m}\text{ht}(\mathbb{T}^{\top}_{u})\geq\ell_{n}^{1/3}\left(\sum_{u=1}^{m}\frac{1}{\sqrt{u}}\right)\right)$
(28) $\displaystyle\leq
A\exp\left(\frac{-f}{A}\right)+A\exp\left(\frac{-\log\left(\frac{n^{1/3}}{f}\right)f^{2}}{A}\right)+\sum_{u=1}^{m}A\exp\left(\frac{-\sqrt{u}f-u\log{\left(\frac{u}{f}\right)}}{A}\right)$
$\displaystyle\leq
A^{\prime}\exp\left(\frac{-f}{A^{\prime}}\right)+A\exp\left(\frac{-\log\left(\frac{n^{1/3}}{f}\right)f^{2}}{A}\right).$

Moreover, by comparison with an integral:

$\sum_{u=1}^{m}\frac{1}{\sqrt{u}}\leq 2\sqrt{m}.$

This shows that the height of the largest component is in fact smaller than
$2\sqrt{m}\ell_{n}^{1/3}$ w.h.p. We can repeat the same argument as before to
show that the number of cuts $\mathcal{P}$ in the largest path verifies:

$\mathbb{P}\left(\mathcal{P}\geq 9f\sqrt{m}\right)\leq
A^{\prime}\exp\left(\frac{-f}{A^{\prime}}\right)+A\exp\left(\frac{-\log\left(\frac{n^{1/3}}{f}\right)f^{2}}{A}\right)+A\exp\left(\frac{-\sqrt{m}}{A}\right).$

By repeating the same arguments recursively, we get for any $l\geq 0$:

$\mathbb{P}\left(\text{ht}(H(\textbf{W},p_{f}))\geq\ell_{n}^{1/3}U_{l+1}\right)\leq
A\exp\left(\frac{-f}{A}\right)+\sum_{u=0}^{t}A\exp\left(\frac{-U_{l}}{A}\right),$
(29)

where:

$U_{0}=m,$

and:

$U_{l+1}=9f\sqrt{U_{l}}.$

The sequence $(U_{l})_{l\geq 0}$ converges to $81f^{2}$. If we define
$R_{l}=U_{l}/(81f^{2})$, then:

$R_{l+1}=\sqrt{R_{l}}.$

It is clear that for $l_{0}=\lceil\log(\ln(R_{0}))\rceil$ we have
$1<R_{l_{0}}\leq e$. Hence:

$\displaystyle\mathbb{P}\left(\text{ht}(H(\textbf{W},p_{f}))\geq\ell_{n}^{1/3}81ef^{2}\right)$
$\displaystyle\leq
A\exp\left(\frac{-f}{A}\right)+\sum_{l=0}^{l_{0}}A\exp\left(\frac{-U_{l}}{A}\right)$
(30) $\displaystyle\leq
A\exp\left(\frac{-f}{A}\right)+\sum_{l=0}^{l_{0}}A\exp\left(\frac{-81f^{2}R_{l_{0}}^{2^{l}}}{A}\right)$
$\displaystyle\leq
A\exp\left(\frac{-f}{A}\right)+\sum_{l=0}^{l_{0}}A^{\prime}\exp\left(\frac{-81f^{2}(l+1)R_{l_{0}}}{A^{\prime}}\right)$
$\displaystyle\leq
A\exp\left(\frac{-f}{A}\right)+A^{\prime\prime}\exp\left(\frac{-f^{2}}{A^{\prime\prime}}\right),$

which finishes the proof. ∎

With a little more work, we could show that the bound given above is in fact
tight, in the sense that for any $\epsilon<1$ the height of the largest
component will be larger than $\frac{f^{1+\epsilon}\ell_{n}^{1/3}}{A}$ w.h.p.
Finally by Theorem 12, Lemma 13 and Theorem 27 we get:

######  Theorem 28.

There exist constants $A^{\prime}>0$ and $A>0$ such that:

$\mathbb{P}(\textnormal{diam}(H(\textbf{W},p_{f}))\geq
A^{\prime}f^{5}\ell_{n}^{1/3})\leq A\exp\left(\frac{-f}{A}\right).$

##  5 Proofs of Theorems 3, 5, 8 and 9

The different statements of Theorem 8 were all proved in the previous
sections. The statements about the weights are shown in Theorem 12, and the
statement about the longest path of small components is a direct corollary of
Theorem 25.

Now we finish the proof of Theorem 9. recall that $(p_{f(i)})_{i\geq 0}$ is a
sequence such that $f(0)=F$ the large constant defined at the end of
Subsection $2.1$, and $f(i+1)=\frac{3}{2}f(i)$ for any $i\geq 0$. We stop at
$f(t_{n})$ the smallest element larger than
$f^{\prime}_{n}=\frac{\ell_{n}^{1/3}}{\log(n)}$. For $0\leq i\leq t_{n}$ we
define the following events, $A>0$ is a large constant:

  1. 1.

$E_{1}(i)$ is the event where $H(\textbf{W},p_{f(i)})$ has size between
$\frac{3f(i)\ell_{n}^{2/3}}{2C}$ and $\frac{5f(i)\ell_{n}^{2/3}}{2C}$.

  2. 2.

$E_{2}(i)$ is the event where the longest path of $H(\textbf{W},p_{f(i)})$ has
length at most $Af(i)^{5}\ell_{n}^{1/3}$.

  3. 3.

$E_{3}(i)$ is the event where every connected component of
$G(\mathcal{V}\setminus\tilde{\mathcal{V}}_{i},p_{f(i+1)})$ has size at most
$\frac{A\ell_{n}^{2/3}}{f(i)^{3/4}}$, and longest path at most
$\frac{A\ell_{n}^{1/3}}{f(i)^{1/4}}$.

Remark that $j\leq 2\log(n)$. Let $r$ be the smallest value such that
$E_{1}(i)$, $E_{2}(i)$, and $E_{3}(i)$ hold for every $r\leq l\leq j$. By
Lemma 10 and a simple computation:

$\text{diam}(H(\textbf{W},p_{f(j)}))\leq\text{diam}(H(\textbf{W},p_{f(r)}))+\frac{A^{\prime}\ell_{n}^{1/3}}{f(r)^{1/5}}\leq
A^{\prime\prime}f(r)^{5}\ell_{n}^{1/3}.$

If $r=i+1$ then one of the events $E_{1}(i)$, $E_{2}(i)$, or $E_{3}(i)$ does
not hold, because if not we would have $r\leq i$. By Theorems 12, 20, 21, 25
and Theorem 28, the probability of one of those events not happening is at
most:

$\mathbb{P}(r=i+1)\leq A\exp\left(\frac{-f(i)^{1/8}}{A}\right).$

Combining the two inequalities above yields:

$\displaystyle\mathbb{E}\left[\text{diam}(H(\textbf{W},p_{f(j)}))\right]$
$\displaystyle\leq\sum_{i=1}^{j-1}A^{\prime\prime}f(i+1)^{5}\ell_{n}^{1/3}\mathbb{P}(r=i+1)$
$\displaystyle\leq\sum_{i=1}^{j-1}A^{\prime\prime}f(i+1)^{5}\ell_{n}^{1/3}A\exp\left(\frac{-f(i)^{1/8}}{A}\right)$
$\displaystyle=O(n^{1/3}).$

The lower bound was provided in Theorem 7. We move now to Theorem 3.

###### Proof of Theorem 3.

Since the diameter is an upper bound of typical distances, by Theorem $1$ we
already have:

$\mathbb{E}[d(U_{f_{n}},V_{f_{n}})]=O(n^{1/3}).$

We need to show now that there exist some constants $\epsilon>0$ and
$\epsilon^{\prime}>0$ such that typical distances in the largest tree in
$\mathcal{T}(\textbf{W},\tilde{p}_{n})$ are larger than $\epsilon n^{1/3}$
with probability at least $\epsilon^{\prime}$. Denote that tree by
$B(\tilde{p}_{n})$. And more generally for any $p>0$ denote the largest tree
in $\mathcal{T}(w,p)$ by $B(p)$. Let $f>0$ be a large constant, and
$p_{f}=\frac{1}{\ell_{n}}+\frac{f}{\ell_{n}^{4/3}}$. For $n$ large enough
$p_{f}<\tilde{p}_{n}$. For a constant $\epsilon>0$, consider the following
events:

  * •

$\mathcal{A}_{1}$ is the event where $B(p_{f})$ is a sub-tree of
$B(\tilde{p}_{n})$, and the size and weight of $B(p_{f})$ are smaller than
$3f\ell_{n}^{2/3}$ for every $n$ large enough.

  * •

$\mathcal{A}_{2}$ is the event where the size and weight of $B(\tilde{p}_{n})$
is larger than $\epsilon n$ for every $n$ large enough.

  * •

$\mathcal{A}_{3}$ is the event where there exist two sub-trees of $B(p_{f})$,
that we denote by $B_{1}(p_{f})$ and $B_{2}(p_{f})$, such that the minimal
distance in $B(p_{f})$ between a node in $B_{1}(p_{f})$ and a node in
$B_{2}(p_{f})$ is larger than $\epsilon n^{1/3}$. Moreover, the sizes and
weights of $B_{1}(p_{f})$ and $B_{2}(p_{f})$ are larger than $\epsilon
n^{2/3}$ for every $n$ large enough.

Then by Theorem 12, for any $\epsilon_{1}>0$, if $f$ is large enough then
$\mathcal{A}_{1}$ holds with probability larger than $1-\epsilon_{1}$.
Moreover, by Theorem 4, there exists $\epsilon>0$ such that $A_{2}$ holds with
high probability. And also, Broutin et al. (2020) show the convergence of the
largest component of $G(\textbf{W},p_{f})$ with graph distances scaled by
$n^{1/3}$ and sizes scaled by $n^{2/3}$ in the Gromov-Hausdorff-Prokhorov
topology to a continuous compact connected graph. We refer to their article
for a detailed analysis of this general result. Here we just emphasize the
fact that their limiting object is a non-trivial compact metric space which
containse two subspaces of mass $\zeta>0$ and at distance at least $\zeta$
with positive probability $\zeta^{\prime}>0$. This result directly implies the
existence of $\epsilon_{3}>0$ such that $A_{3}$ holds with probability at
least $\epsilon_{3}$.

Let
$\mathcal{A}(\epsilon)=\mathcal{A}_{1}\cap\mathcal{A}_{2}\cap\mathcal{A}_{3}$.
By the discussion above, there exists two constants $\epsilon>0$ and
$\epsilon_{4}>0$ such that, for a constant $f>0$ large enough,
$\mathcal{A}(\epsilon)$ holds with probability at least $\epsilon_{4}$. This
shows that there exists some $\epsilon_{5}>0$ such that, by denoting the total
weight of a graph $G$ by $W(G)$, we have 444Here we just set the weights and
sizes to $0$ if $B_{1}(p_{f})$ or $B_{2}(p_{f})$ do not exist:

$\mathbb{E}\left[W\left(B_{1}(p_{f})\right)\right]\geq\epsilon_{5}\mathbb{E}\left[W\left(B(p_{f})\right)\right].$
(31)

For $\tilde{p}_{n}\geq p\geq p_{f}$, let $B_{1}(p)$ be the sub-tree of
$B(\tilde{p}_{n})$ obtained by applying Kruskal’s algorithm to $B_{1}(p_{f})$
between $p_{f}$ and $p$. And define $B_{2}(p)$ similarly. Clearly the distance
between $B_{1}(\tilde{p}_{n})$ and $B_{2}(\tilde{p}_{n})$ is larger than
$\epsilon_{3}n^{1/3}$. It is thus sufficient to show that the sizes of
$B_{1}(\tilde{p}_{n})$ and $B_{2}(\tilde{p}_{n})$ are on expectation
proportional to $n$. By symmetry it is sufficient to show this for
$B_{1}(\tilde{p}_{n})$.

Let $(r_{1},r_{2},r_{3},...)$ be the sequence of increasing values between
$p_{f}$ and $\tilde{p}_{n}$ at which a new edge is added by Kruskal’s
algorithm to $(B(r_{i}^{-}))_{i\geq 1}$. At each value $r_{i}$, an edge is
created between $B(r_{i}^{-})$ and the rest of
$\mathcal{T}(\textbf{W},r_{i}^{-})$. And by the properties of exponential
random variables, the probability that such an edge gets connected to
$B_{1}(r_{i}^{-})$ is equal to

$\frac{W(B_{1}(r_{i}^{-}))}{W(B(r_{i}^{-}))},$

Hence the process of weights

$(W(B_{1}(r_{i}^{-})),W(B(r_{i}))-W(B_{1}(r_{i}^{-})))_{i\geq 1},$

corresponds to a Polya Urn with a ball with of random weight is added at each
step, it is easy to check by induction that if at step $i$, there exists
$\epsilon>0$ such that:

$\mathbb{E}[W(B_{1}(r_{i}^{-}))]=\epsilon\mathbb{E}[W(B(r_{i}^{-}))],$

Then at step $i+1$, a connected component $C(i)$ is added and we get:

$\displaystyle\mathbb{E}[W(B_{1}(r_{i+1}^{-}))]$
$\displaystyle=\epsilon\mathbb{E}[W(B(r_{i}^{-}))]+\epsilon\mathbb{E}[W(C(i))]$
$\displaystyle=\epsilon\mathbb{E}[W(B(r_{i+1}^{-})],$

with the same $\epsilon$ of step $i$. We know that (for instance by Theorem
4), there exists $\epsilon_{8}>0$ such that for $n$ large enough

$\mathbb{E}\left[W\left(B\left(\tilde{p}_{n}\right)\right)\right]\geq\epsilon_{8}n.$

Given that the event $\mathcal{A}$ holds with positive probability, this,
alongside Equation 31, shows that there exists $\epsilon_{6}>0$ such that:

$\mathbb{E}\left[W\left(B_{1}\left(\tilde{p}_{n}\right)\right)\right]\geq\epsilon_{6}n.$
(32)

And the same also holds for $B_{2}$. Finally, we use this lower bound on the
weight in order to get a lower bound on what we actually need, the size.

Recall that the node weights depend implicitly on $n$. Suppose that there
exists an $N>0$ and subsets $(\mathcal{S}_{n})_{n\geq N}$ of the nodes such
that:

$\sum_{k\in\mathcal{S}_{n}}w_{k}\geq\epsilon_{6}n,$

for every $n\geq N$, but the sizes of those sets verify
$|\mathcal{S}_{n}|=o(n)$. Let $w_{V_{n}}$ be a uniformly chosen node from
$(w_{1},w_{2},...,w_{n})$. We thus have:

$\mathbb{E}[\mathbbm{1}(V_{n}\in S_{n})w_{V_{n}}]\geq\epsilon_{7}.$

Conditions $i$ and $iv$ in Conditions 1 imply by Theorem $3.6$ in Billingsley
(1968) that the $(w_{V_{n}})_{n\geq N}$ are uniformly integrable. However, by
definition of $(\mathcal{S}_{n})_{n\geq N}$ we also have $\mathbb{P}(V_{n}\in
S_{n})=o(1)$. This is in contradiction with the definition of uniform
integrability . Hence no such sets exist, and Equation 32 implies the
existence of $\epsilon_{7}$ such that:

$\mathbb{E}\left[\middle|B_{1}\left(\tilde{p}_{n}\right)\middle|\right]\geq\epsilon_{7}n,$

for any $n$ large enough. We have thus shown that there exist two sub-trees,
$B_{1}\left(\tilde{p}_{n}\right)$ and $B_{1}\left(\tilde{p}_{n}\right)$, of
$B\left(\tilde{p}_{n}\right)$ of sizes proportional to $n$ and such that the
distance between the two sub-trees is larger than $\epsilon_{7}n$ on-
expectation. This finishes the proof. ∎

Finally we prove the same result for the trees related to statistical physics.
Meaning we take the minimum spanning tree of the largest component of
$G(\textbf{W},\tilde{p}_{n})$ with i.i.d capacities on its edges.

###### Proof of Theorem 5.

Under Conditions 1, and for $n$ large enough, we can also construct that
minimal spanning tree by using an edge deletion algorithm with exponentially
distributed edge capacities. Fix $c>1$ and to each non-oriented edge
$\\{i,j\\}$, $i\neq j$, associate the random capacity
$E^{\prime}_{\\{i,j\\}}$, which is an exponential random variable of rate $1$.
The capacities are then used to create a sequence of graphs. First keep each
edge independently with probability
$p_{\\{i,j\\}}=\frac{w_{i}w_{j}c}{\ell_{n}}=o(n^{-1/3})$. Once this operation
is done we obtain a graph $G^{\prime}(\textbf{W},+\infty)$. We can then
construct an increasing sequence of graphs $(G^{\prime}(\textbf{W},p))_{p\geq
0}$ for inclusion by letting $G^{\prime}(\textbf{W},p)$ be the subgraph of
$G^{\prime}(\textbf{W},+\infty)$ with edge capacities verifying:

$\left\\{\\{i,j\\}|E^{\prime}_{\\{i,j\\}}\leq p\right\\}.$

Under Conditions 1:

$1-\exp\left(\frac{-w_{i}w_{j}c}{\ell_{n}}\right)=p_{\\{i,j\\}}\left(1+O(p_{\\{i,j\\}})\right).$

Moreover, if $\\{i,j\\}\neq\\{i^{\prime},j^{\prime}\\}$ then the edge
capacities $E^{\prime}_{\\{i,j\\}}$ and
$E^{\prime}_{\\{i^{\prime},j^{\prime}\\}}$ are independent. This implies that
for any $\epsilon>0$ and for $n$ large enough $G^{\prime}(\textbf{W},+\infty)$
can be coupled edge by edge with two graphs
$G(\textbf{W},\frac{c+\epsilon\ell_{n}^{-1/3}}{\ell_{n}})$ and
$G(\textbf{W},\frac{c-\epsilon\ell_{n}^{-1/3}}{\ell_{n}})$ in such a way that:

$G\left(\textbf{W},\frac{c-\epsilon\ell_{n}^{-1/3}}{\ell_{n}}\right)\subset
G^{\prime}(\textbf{W},+\infty)\subset
G\left(\textbf{W},\frac{c+\epsilon\ell_{n}^{-1/3}}{\ell_{n}}\right).$

We say that $G^{\prime}(\textbf{W},+\infty)$ is asymptotically equivalent to
$G(\textbf{W},\tilde{p}_{n})$. Generally, for every $p\geq 0$,
$G^{\prime}(\textbf{W},p)$ is asymptotically equivalent to
$G(\textbf{W},(1-e^{-p})\tilde{p}_{n})$. Now for each $p$, consider the forest
$\mathcal{T}^{\prime}(\textbf{W},p)$ constructed by the edge deletion
algorithm: Sort the edges $(\\{i,j\\})_{i\leq n,j\leq n}$ of
$G^{\prime}(\textbf{W},p)$ by decreasing order of their capacities
$(E^{\prime}_{\\{i,j\\}})_{i\leq n,j\leq n}$. Then starting from the first
edge, only keep an edge if removing it would disconnect a connected component.
By construction, for any $p\leq\infty$, $\mathcal{T}^{\prime}(\textbf{W},p)$
is the minimum spanning forest of $G^{\prime}(\textbf{W},p)$ with respect to
the capacities $(E^{\prime}_{\\{i,j\\}})_{i\leq n,j\leq n}$. Hence,
$(\mathcal{T}^{\prime}(\textbf{W},p))_{p\geq 0}$ is an increasing process of
spanning trees for $(G^{\prime}(\textbf{W},p)_{p\geq 0}$. Hence, if we define
$\mathcal{A}^{\prime}(\epsilon)$ similarly to $\mathcal{A}(\epsilon)$ but for
the forests $(\mathcal{T}^{\prime}(\textbf{W},p))_{p\geq 0}$, it is sufficient
to prove that there exist $\epsilon>0$ and $\epsilon^{\prime}>0$ such that
$\mathcal{A}^{\prime}(\epsilon)$ holds with probability at least
$\epsilon^{\prime}$. This is true because $\mathcal{A}(\epsilon)$ holds with
probability at least $\epsilon^{\prime}$ for some $\epsilon^{\prime}>0$ and
$\epsilon>0$ and because of the asymptotic equivalence relation between
$G(\textbf{W},(1-e^{-p})\tilde{p}_{n})$ and $G^{\prime}(\textbf{W},p)$ for
every $p\geq 0$, and between $G^{\prime}(\textbf{W},+\infty)$ and
$G(\textbf{W},\tilde{p}_{n})$. ∎

## Bibliography

  * Addario-Berry and Sen [2019] L. Addario-Berry and S. Sen.  Geometry of the minimal spanning tree of a random $3$-regular graph.  _arXiv preprint arXiv:1810.03802_ , 2019.
  * Addario-Berry et al. [2009] L. Addario-Berry, N. Broutin, and B. Reed.  Critical random graphs and the structure of a minimum spanning tree.  _Random Structures Algorithms_ , 35(3):323–347, 2009.  ISSN 1042-9832.  doi: 10.1002/rsa.20241.  URL https://doi.org/10.1002/rsa.20241.
  * Addario-Berry et al. [2017] L. Addario-Berry, N. Broutin, C. Goldschmidt, and G. Miermont.  The scaling limit of the minimum spanning tree of the complete graph.  _Ann. Probab._ , 45(5):3075–3144, 2017.  ISSN 0091-1798.  doi: 10.1214/16-AOP1132.  URL https://doi.org/10.1214/16-AOP1132.
  * Aldous [1990] D. Aldous.  A random tree model associated with random graphs.  _Random Structures & Algorithms_, 1(4):383–402, 1990.
  * Aldous [1997] D. Aldous.  Brownian excursions, critical random graphs and the multiplicative coalescent.  _Ann. Probab._ , 25(2):812–854, 1997.  ISSN 0091-1798.  doi: 10.1214/aop/1024404421.  URL https://doi.org/10.1214/aop/1024404421.
  * Aldous and Limic [1998] D. Aldous and V. Limic.  The entrance boundary of the multiplicative coalescent.  _Electron. J. Probab._ , 3:No. 3, 59 pp. 1998.  ISSN 1083-6489.  doi: 10.1214/EJP.v3-25.  URL https://doi.org/10.1214/EJP.v3-25.
  * Ben-Hamou et al. [2018] A. Ben-Hamou, Y. Peres, and J. Salez.  Weighted sampling without replacement.  _Brazilian Journal of Probability and Statistics_ , 32(3):657–669, 2018.
  * Bernstein [1924] S. Bernstein.  On a modification of Chebyshev’s inequality and of the error formula of laplace.  _Ann. Sci. Inst. Sav. Ukraine, Sect. Math_ , 1(4):38–49, 1924.
  * Bhamidi and Sen [2020] S. Bhamidi and S. Sen.  Geometry of the minimal spanning tree in the heavy-tailed regime: new universality classes.  _arXiv preprint arXiv:2009.10696_ , 2020.
  * Bhamidi et al. [2010] S. Bhamidi, R. van der Hofstad, and J. S. H. van Leeuwaarden.  Scaling limits for critical inhomogeneous random graphs with finite third moments.  _Electron. J. Probab._ , 15:no. 54, 1682–1703, 2010.  doi: 10.1214/EJP.v15-817.  URL https://doi.org/10.1214/EJP.v15-817.
  * Bhamidi et al. [2018] S. Bhamidi, R. van der Hofstad, and S. Sen.  The multiplicative coalescent, inhomogeneous continuum random trees, and new universality classes for critical random graphs.  _Probability Theory and Related Fields_ , 170(1-2):387–474, 2018.
  * Billingsley [1968] P. Billingsley.  _Convergence of probability measures_.  John Wiley & Sons, Inc., New York-London-Sydney, 1968.
  * Bollobás et al. [2007] B. Bollobás, S. Janson, and O. Riordan.  The phase transition in inhomogeneous random graphs.  _Random Structures and Algorithms_ , 31:3–122, 2007.
  * Boucheron et al. [2013] S. Boucheron, G. Lugosi, and P. Massart.  _Concentration inequalities_.  Oxford University Press, Oxford, 2013.  ISBN 978-0-19-953525-5.  doi: 10.1093/acprof:oso/9780199535255.001.0001.  URL https://doi.org/10.1093/acprof:oso/9780199535255.001.0001.  A nonasymptotic theory of independence, With a foreword by Michel Ledoux.
  * Braunstein et al. [2007] L. A. Braunstein, Z. Wu, Y. Chen, S. V. Buldyrev, T. Kalisky, S. Sreenivasan, R. Cohen, E. Lopez, S. Havlin, and H. E. Stanley.  Optimal path and minimal spanning trees in random weighted networks.  _International Journal of Bifurcation and Chaos_ , 17(07):2215–2255, 2007.
  * Broutin et al. [2020] N. Broutin, T. Duquesne, and M. Wang.  Limits of multiplicative inhomogeneous random graphs and Lèvy trees: Limit theorems.  _arXiv preprint arXiv:2002.02769_ , 2020.
  * Chen et al. [2006] Y. Chen, E. López, S. Havlin, and H. E. Stanley.  Universal behavior of optimal paths in weighted networks with general disorder.  _Physical review letters_ , 96(6):068702, 2006\.
  * Chung and Lu [2006] F. Chung and L. Lu.  _Complex graphs and networks_ , volume 107 of _CBMS Regional Conference Series in Mathematics_.  Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 2006.  ISBN 978-0-8218-3657-6; 0-8218-3657-9.  doi: 10.1090/cbms/107.  URL https://doi.org/10.1090/cbms/107.
  * Frieze [1985] A. M. Frieze.  On the value of a random minimum spanning tree problem.  _Discrete Applied Mathematics_ , 10(1):47–56, 1985.
  * Janson [2010] S. Janson.  Asymptotic equivalence and contiguity of some random graphs.  _Random Structures & Algorithms_, 36(1):26–45, 2010.
  * Kruskal [1956] J. B. Kruskal.  On the shortest spanning subtree of a graph and the traveling salesman problem.  _Proceedings of the American Mathematical society_ , 7(1):48–50, 1956.
  * Norros and Reittu [2006] I. Norros and H. Reittu.  On a conditionally Poissonian graph process.  _Adv. in Appl. Probab._ , 38(1):59–75, 2006.  ISSN 0001-8678.  doi: 10.1239/aap/1143936140.  URL https://doi.org/10.1239/aap/1143936140.
  * Prim [1957] R. C. Prim.  Shortest connection networks and some generalizations.  _The Bell System Technical Journal_ , 36(6):1389–1401, 1957.
  * Safsafi [2020] O. Safsafi.  Exponential bounds for inhomogeneous random graphs with finite fourth moment.  _arXiv preprint arXiv:2001.00882_ , 2020.
  * Stegehuis et al. [2017] C. Stegehuis, R. van der Hofstad, A. Janssen, and J. van Leeuwaarden.  Clustering spectrum of scale-free networks.  _Physical Review E_ , 96(4), 10 2017.  ISSN 2470-0045.  doi: 10.1103/PhysRevE.96.042309.
  * van der Hofstad et al. [2018] R. van der Hofstad, S. Kliem, and J. van Leeuwaarden.  Cluster tails for critical power-law inhomogeneous random graphs.  _Journal of Statistical Physics_ , 171(1):38–95, 4 2018.  ISSN 0022-4715.  doi: 10.1007/s10955-018-1978-0.
  * Vazirani [2001] V. V. Vazirani.  _Approximation algorithms_.  Springer-Verlag, Berlin, 2001.  ISBN 3-540-65367-8.
  * Wu et al. [2006] Z. Wu, L. A. Braunstein, S. Havlin, and H. E. Stanley.  Transport in weighted networks: partition into superhighways and roads.  _Physical Review Letters_ , 96(14):148702, 2006\.