As mentioned at the beginning of this section, for our methods to work, we require the network to satisfy a few conditions that are likely to hold for some time. If one or more of these conditions are not met, we stop the process. Let $s$ be the function in the statement of Theorem 4, and introduce the stopping times:

$T_{\text{ext}}$ the extinction time of the infection process,

$T_{\text{hit}}$ the smallest time $t$ such that $M(t) \ge s(a)$,

$T_{\text{bad}}^{\text{tree}}$ the smallest time $t$ such that either $G_t$ contains an (undirected) cycle, or an edge $(i, j) \in G_{t-}$ is resampled as present (following Rule (1)),

$T_{\text{bad}}^{\text{deg}}$ the smallest time $t$ such that a weak vertex $i$ is connected to at least $1/(8\lambda^2)$ weak vertices in $G_t$ through present edges.

We also advance that there is an additional stopping time $T_{\text{bad}}^{\text{conn}}$, which is far more technical and will be defined in the next section, see (104), since it requires several elements which will be introduced when defining the scoring function. The process stops at time $T$, which is defined as

$$T = T_{\text{bad}} \wedge T_{\text{hit}} \wedge T_{\text{ext}}, \quad \text{with} \quad T_{\text{bad}} = T_{\text{bad}}^{\text{tree}} \wedge T_{\text{bad}}^{\text{deg}} \wedge T_{\text{bad}}^{\text{conn}}.$$

The intuition behind the stopping time $T$ is that we run the process until either the network stops behaving nicely ($T_{\text{bad}}$), the infection goes extinct ($T_{\text{ext}}$), or the score becomes too large ($T_{\text{hit}}$). As will be seen later, the latter condition includes the critical event in which the infection reaches a star, or a star vertex is incorporated to $G_t$. In particular $G_t$ contains only nonstar vertices at times $t < T_{\text{hit}}$. Moreover, at time $t < T_{\text{bad}}^{\text{tree}}$, the network $G_t$ consists of a tree in which all edges point outwards from the root, which is the starting infected vertex $i_0$. Once again, we stress that the orientation of the edges is used only in the construction of $G_t$ and the scoring, not for the propagation of the epidemics inside $G_t$.

At this point it is worth mentioning that once a vertex $i$ becomes visited, we begin tracking its weak neighbourhood (following Rules (6) and (7)). After an update of $i$, with large probability all edges incident to $i$ in $G_t$ become absent. Thus, if $i$ was healthy at the time of the update, it becomes inaccessible for the infection, never to be reached again. One might question whether tracking the weak neighbours of $i$ could prematurely halt the process by reintroducing an absent edge or creating a loop in $G_t$. However, as we demonstrate in the last section, even in such cases, the infection is more likely to reach a star or extinction before such events occur.

*Score attached to weak vertices.* We begin describing the score given to configurations as long as the network behaves nicely, that is, for all $t < T_{\text{bad}}$. The general score $M(t)$ is divided as

$$M(t) = M_{\text{strong}}(t) + M_{\text{weak}}(t),$$

with $M_{\text{strong}}(t)$ and $M_{\text{weak}}(t)$ the scores attached to strong and weak vertices. In order to define $M_{\text{weak}}(t)$ we use that locally around a weak vertex the graph has a tree structure and methods from [16] developed for the contact process on static trees can be adapted to our situation. We begin by recalling [16], where the contact process was studied on a tree $t$
with degrees bounded by $1/(8\lambda^2)$. In this work the authors associate a scoring $W_j^{\text{static}}(t)$ to each vertex $j$, defined as

$$W_j^{\text{static}}(t) = \sum_{\substack{i \in t \\ i \text{ infected}}} (2\lambda)^{d_t(i,j)},$$

where $d_t$ is the graph distance within $t$. In order to prove that this scoring is a super-martingale, it is shown that each $W_j^{\text{static}}(t)$ has average infinitesimal increase bounded by $-W_j^{\text{static}}(t)/4$. It follows that for any choice of nonnegative weights $w_j$ on $t$, the process

$$\sum_{j \in t} w_j W_j^{\text{static}}(t) = \sum_{i,j \in t} (2\lambda)^{d_t(i,j)} w_j \mathbf{1}_{i \text{ infected at time } t} \quad (80)$$

is a non-negative supermartingale. Observe that the process in (80), being a double sum, can be written as

$$\sum_{j \in t} w_j W_j^{\text{static}}(t) = \sum_{\substack{i \in t \\ i \text{ infected}}} M_i^{\text{static}}(t)$$

where, for each $i \in t$,

$$M_i^{\text{static}}(t) = \sum_{j \in t} (2\lambda)^{d_t(i,j)} w_j \quad (81)$$

serves as a dual scoring function. Maybe surprisingly, we can use the same functions in the context of evolving graphs with only minor modifications.

Let $t \ge 0$ and $i \in G_t$ a weak vertex. We define $t(t) \subseteq G_t$ as the subgraph induced by the weak vertices, where we only keep the present edges (which for all purposes will be taken unoriented). The resulting network corresponds to a collection of trees with maximum degree at most $1/(8\lambda^2)$, since we assume that $t < T_{\text{bad}}^{\text{deg}}$, where we define the usual graph distance $d_t(i, j)$, with the convention $d(i, j) = \infty$ if $i$ and $j$ are not connected.

Observe that vertices in $t$ that are not labelled *visited*, have been revealed as neighbours of visited vertices, but have not revealed their own neighbourhoods yet. These vertices, which we call *pending leaves*, prevent us from choosing $w_j = s(j/N)$ in (80), since upon being infected they would reveal new neighbours (following Rule (6)) and thus increase the score in average. To prevent this, we replace $w_j$ with a slightly different scoring whose role is to overestimate the possible scoring obtained after revealing a new part of the structure. Let $c \ge 4$, which will be further specified later, and assume that $s$ satisfies the assumptions of Theorem 4 for this value of $c$.

We define the function

$$\tilde{s}_i := \begin{cases} s_i & \text{if } i \text{ is visited,} \\ \frac{c}{c-2}s_i & \text{if } i \text{ is a pending leaf,} \end{cases}$$

where $s_i = s(i/N)$. From the constraint $c \ge 4$, we thus have $s_i < \tilde{s}_i \le 2s_i$. We now define for each $j$ the individual scoring $M_j$ similarly to (81) as

$$M_i(t) = \sum_{j \in t} (2\lambda)^{d(i,j)} \tilde{s}_j \quad (82)$$
under the assumption that $\lambda < 1/2$. Observe that from this assumption and the choice $d(i,j) = \infty$ for non-connected vertices, the sum can be restricted to the connected component of $i$. We thus define

$$M_{\text{weak}}(t) = \sum_{\substack{i \in t \\ i \text{ infected}}} M_i(t).$$

*Evolution of the process by saturation of vertices and edges.* As in the process introduced in the previous section, vertex saturation is a state akin to being infected, but in which vertices cannot recover. When a vertex becomes saturated, it remains in this state, acting as a source of infection, until it updates. Even though the intuition is the same as in the proof of Theorem 3, the conditions for saturation differ, and not all vertices can become saturated. We also maintain the intuition for edge saturation, which occurs when an edge connects two saturated vertices, allowing the use of the edge for infection transmission to be ignored. Before defining the exact conditions for saturation we introduce more notation.

Recall the definition of $t$ as introduced in the previous subsection and let $\tilde{t}$ be an arbitrary subset of $t$. We write

$$M_{\tilde{t}}(t) := \sum_{\substack{k \in \tilde{t} \\ k \text{ infected}}} M_k(t) \qquad (83)$$

to refer to the total scoring of $\tilde{t}$. Define also $t_j$ as the connected component of $j$ in $t$ (for $j \in G_t$ weak). With this notation, for any strong vertex $i \in G_t$, define $R_{ij}(t)$, for $j \in G_t$, as:

$$R_{ij}(t) := \begin{cases} 0 & \text{if } j \text{ is strong slow,} \\ \frac{\lambda}{\kappa_i + \kappa_j} & \text{if } j \text{ is strong quick,} \\ \frac{16\lambda M_{t_j}(t)}{s_j} & \text{if } j \text{ is weak.} \end{cases}$$

Using these functions define

$$R_i(t) := R_i^{\text{strong}}(t) + R_i^{\text{weak}}(t) := \sum_{j \text{ strong} \sim i} R_{ij}(t) + \sum_{j \text{ weak} \sim i} R_{ij}(t) \qquad (84)$$

where $j \sim i$ means, as usual, that $i$ and $j$ are neighbours in $G_t$ (regardless of orientation). Finally, for a strong slow vertex $i \in G_t$, let $N_i^{ss}$ be the number of neighbours of $i$ in the network that are strong slow. We can now introduce the evolution rules concerning saturated vertices and edges.

**Rule (8):** A strong vertex $i \in G_t$ is instantly declared *infected and saturated* as soon as any one of the following two conditions is met:

(i) $R_i(t) \ge 1/4$.

(ii) $i$ is incident to a weak vertex $j$ (through a present edge), and some vertex $k \in t_j$ infects another strong vertex $i'$.

If $i$ is strong slow, we also declare it *infected and saturated* if

(iii) since its last update it has *infected another strong slow vertex* or has been *infected by another strong slow vertex*,

(iv) $N_i^{ss}(t) \ge \frac{3\kappa_i T_i^{\text{loc}}}{8\lambda}$, where $T_i^{\text{loc}}$ is as in Definition 3.
Rule (9): Saturated vertices do not recover, and can only desaturate when updating. When a saturated vertex $i$ updates, if none of the conditions introduced in Rule (8) hold, then the vertex is no longer saturated and becomes just infected.

Rule (10): When a strong slow vertex $i$ infects another strong slow vertex $j$, the edge between them becomes *saturated*.

The reader might wonder why, as opposed to the proof of Theorem 3 we do not need to “split” the slow strong edges within $G_t$. To answer this question recall that the splitting of edges was used to handle the possibility of reinfection between slow vertices, which for this process is impossible. We argue as follows: suppose that the strong slow edge $(i, j)$ is incorporated to the network at some time $t$, at which time $j$ must have been revealed as a (healthy) neighbour of $i$. Since the network is a tree, for $j$ to become infected for the first time, it must receive the infection from $i$. At that point, both $i$ and $j$ become saturated (following Condition (iii) in Rule (8)). For $j$ to reinfect $i$ later on, $i$ must be healthy, and hence must have updated at some point. However, in that case, the edge $(i, j)$ would have become absent, thereby disconnecting $i$ and $j$.

Observe that the definition of saturation in Theorem 3 involves conditions analogous to (i), (iii), and (iv) in Rule (8). Condition (ii), however, is new and might be quite astonishing with its long distance interaction, which does not even require $i$ to be infected in the first place, see for example Figure 8. It is however extremely useful, as it ensures that for a strong unsaturated vertex $i$, the weak trees $t_j$ attached to it are not connected to any other strong vertex from which it could receive infections.

<figure><img src="image_10.png" /><figcaption>FIGURE 8. In the picture, $i$ is connected to the weak vertex $j$, and the vertices in $t_j$ are depicted with a wide border. There is one infected vertex in $t_j$ attempting to infect the strong vertex $i'$ through a *clogged* edge. If it were to succeed, then $i$ would immediately become infected and saturated. Observe that the vertex at the right also could infect $i'$, but in that case nothing would happen to $i$, because of the absent edge (with an $X$) on its path to $i$.</figcaption></figure>

A first application of Condition (ii) is the justification of the new choice for the function $R_i(t)$ in this proof. Observe that it is similar to the one introduced in the proof of Theorem 3, the main difference being the introduction of the term $R_{ij}(t) = 16\lambda M_{t_j}(t)/s_j$ for weak vertices. Recall that the role of $R_{ij}$ is to provide an upper bound for the probability that the vertex $j$ will later infect $i$ before the connection is refreshed. With this in mind,
* suppose that $i$ is unsaturated and connected to $j$, and in what follows conditions (i)-(iv) are never met (since upon becoming saturated, infections from $j$ to $i$ are pointless). Because the event in condition (ii) does not occur, the tree $t_j$ cannot be directly connected to any other strong vertex $i'$, and hence in our interpretation of $R_{ij}$ we assume that the infection is “trapped within $t_j$”.

* In the next section we show that, when neglecting infections between strong and weak vertices, $M_{\text{weak}}$ is a supermartingale, and in fact,

$$ \frac{1}{dt} \mathbb{E}[M_{t_j(t+dt)}(t+dt) - M_{t_j(t)}(t)|\mathcal{F}_t] \le -\frac{1}{8} M_{t_j(t)}(t), $$

where $t_j(t)$ and $t_j(t+dt)$ are the connected components of $j$ in $t$ at times $t$ and $t+dt$, respectively. Using almost identical computations it can be proved that if we allow for infections between $i$ and $j$, a similar upper bound is obtained if we replace $M_{t_j(t)}(t)$ by

$$ \tilde{M}(t) := M_{t_j(t)}(t) + \mathbf{1}_i \text{ infected at time } t \sum_{l \in t} (2\lambda)^{d(l,j)-1} \tilde{s}_l. $$

If we were to start the infection process at time $t$ from a given configuration in which $i$ is healthy, then, using the stopping time $\tilde{T} \ge t$ in which either the infection dies out within $t_j$, or $i$ becomes infected, we arrive at

$$ \frac{s_j}{2\lambda} \mathbb{P}(j \text{ infects } i | \mathcal{F}_t) \le \mathbb{E}(\tilde{M}(\tilde{T}) | \mathcal{F}_t) \le \tilde{M}(t) = M_{t_j(t)}(t), $$

thus showing that $R_{ij}$ fits the intended role.

* When $i$ first infects $j$, the value of $R_{ij}(t)$ will be of order $\lambda$, and the same will be typically true when the infection propagates throughout $t_j$. This is an improvement over the expression $\lambda/(\kappa_i + \kappa_j)$ used for strong quick vertices or in the proof of Theorem 3.

*Score attached to strong vertices and edges.* We now address the remaining expression $M_{\text{strong}}(t)$ from the decomposition $M(t) = M_{\text{weak}}(t) + M_{\text{strong}}(t)$, which is analogous to the scoring introduced in the proof of Theorem 3, so in particular we use the same notation: We recall the functions $\pi$ and $T^{\text{loc}}$ introduced in Definition 3,

$$ \begin{aligned} \pi(x) &= \int_0^1 \frac{p(x, y)}{\kappa(x) + \kappa(y)} dy, \\ T^{\text{loc}}(x) &= \max \left\{ 8, \frac{8}{3\kappa(x)}, 16\lambda^2 \frac{\pi(x)}{\kappa(x)} \right\}, \end{aligned} $$

and take $a(\lambda)$ and $s(x)$ satisfying the hypotheses of Theorem 4, that is, (48), (49), and (50), as well as assumptions (H1) and (H2). As in the previous proof we use the subscript notation when considering the corresponding functions defined on $\{1, \dots, N\}$. We now define the scoring $M_{\text{strong}}$ as

$$ M_{\text{strong}}(t) := \sum_{i \in G_t \text{ strong}} m_i(t) + \sum_{\substack{(i,j) \text{ present} \\ \text{strong slow}}} s_j + t_j + u_j, \quad (85) $$
with

$$m_i(t) := \begin{cases} s_i + t_i & \text{if } i \text{ is infected saturated,} \\ s_i + 4R_i(t)t_i & \text{if } i \text{ is infected unsaturated,} \\ 2R_i(t)(s_i + t_i) & \text{if } i \text{ is healthy,} \end{cases}$$

and again, for some $r \ge 3/2$ to be fixed later,

$$t_i := \frac{s_i}{r\kappa_i T_i^{\text{loc}}}, \quad u_i = \frac{t_i}{3}.$$

Regarding the scoring we point out the following useful facts:

* Since $T_j^{\text{loc}} \ge \frac{8}{3\kappa_i}$ and $T_j^{\text{loc}} \ge 8$, it easily follows from the definition of $t_i$ that inequalities

$$t_i \le \frac{s_i}{4} \quad \text{and} \quad \kappa_i t_i \le \frac{s_i}{8r} \qquad (86)$$

hold as in the previous section. Similarly, as in (61), for any strong slow vertex $i$,

$$\frac{8\lambda}{3\kappa_i T_i^{\text{loc}}} \sum_{j \le a_{\text{stsl}} N} p_{ij} \le \frac{1}{3}, \qquad (87)$$

by exploiting the fact that $a_{\text{stsl}} \le a_{\text{slow}}$. As a last adaptation of previous computations, we can require that $c \ge 4r$ (by fixing $c$ after fixing $r$), which gives

$$\sum_{j<a_{\text{stsl}}N} p_{ij}(s_j + t_j + u_j) \le u_i, \qquad (88)$$

analogously to (65).

* As in the previous proof, the score related to the connection between strong slow vertices is attached to the strong slow edges rather than the vertices (because $R_{ij} = 0$ if both vertices are strong slow). Note that this is one of the few instances where the orientation of an edge $(i, j) \in G_t$ does matter, since the score value depends on the endpoint $j$ alone. Again, this scoring reflects the idea that $j$ is very likely to get infected by $i$.

* A star vertex $j$ can be incorporated to $G_t$ without being infected only through revealing a present strong slow edge $(i, j)$, with associated score $s_j+t_j+u_j > s(a)$. If this happens we instantly reach $T_{\text{hit}}$.

* The scoring of strong vertices only depend on the weak vertices through $R^{\text{weak}}$, while the scoring of weak vertices do not depend on the strong vertices.

* Non visited vertices have null score. This follows since the only non visited vertices that can be found in $G_t$ are either healthy weak vertices (for which the scoring is null), or strong slow vertices with a single neighbour $j \in G_t$, which is also strong slow (so the score is null since $R_{ij} = 0$ if $j$ is strong slow). A similar analysis shows that when a strong vertex $i$ reveals new neighbours, it does not increase its score.

**Supermartingale property of $M(t)$**. In this section we compute the average infinitesimal change of $M(t)$ due to the evolution of the process and show that it is a nonnegative supermartingale. Before the computations we point out two important facts:
(1) The scoring $M(t)$ has only been defined at times $t$ satisfying $t < T_{\text{bad}}$, so for the scoring to be useful, we need to define what the scoring should be when reaching a configuration giving $t = T_{\text{bad}}$. Fortunately, since $M(t)$ is nonnegative, it is enough to set $M(T_{\text{bad}}) = 0$ without any risk of losing the supermartingale property.

(2) We have not yet defined the stopping time $T_{\text{bad}}^{\text{conn}}$. The definition will be given at the end of this section, but we advance that it comprises the scenarios in which strong vertices are connected to too many weak trees where the infection has proliferated.

As in the proof of Theorem 3, we show that $M(t)$ is a supermartingale by fixing $t > 0$, and writing the expected infinitesimal change of the score

$$ \frac{1}{dt} \mathbb{E}[M(t + dt) - M(t)|\mathfrak{F}_t] \qquad (89) $$

as a large sum of terms associated with the effects that a single transition event of the process have on the scoring of the vertices and edges. In what follows we assume that:

* At time $t$ we have not yet stopped the process. Even though considering times $t \ge T$ is harmless for the supermartingale property (because in that case $M(t+dt) - M(t) = 0$), it is important for our computations to obtain strictly negative upper bounds for (89).

* The transition events considered preserve the tree event (that is $t + dt < T_{\text{bad}}$). Again, this is a harmless assumption since by definition $M(T_{\text{bad}}) = 0$.

Analogously to the proof of Theorem 3, we group these terms into contributions, many of them identical to the ones presented in the previous section. We divide these contributions according to the types of vertices involved in the events taking place. In order to avoid cluttered notation, we will drop the dependence on time for all functions for the rest of this section, provided there is no risk of confusion.

(i) Contributions from events that only involve weak vertices.

For any fixed $t \ge 0$ let $\tilde{t}$ be a connected component of $t$ at time $t$. Our main goal will be to show that the expressions appearing in

$$ \frac{1}{dt} \mathbb{E}[M_{\text{weak}}(t + dt) - M_{\text{weak}}(t)|\mathfrak{F}_t] \qquad (90) $$

as a result of events that involve vertices in $\tilde{t}$, and their interactions with other weak vertices, can be upper bounded by $-\frac{1}{8}M_{\tilde{t}}(t)$, where $M_{\tilde{t}}$ was defined in (83). We first observe that because we are assuming $t + dt < T_{\text{bad}}$, we exclude the possibility of connecting vertices in $\tilde{t}$ to other vertices in $G_t \setminus \tilde{t}$ and hence the score of the latter vertices is unaffected. On the other hand, weak vertices that are added to $\tilde{t}$ are healthy, so their score is not counted when computing $M_{\text{weak}}(t + dt)$. Hence, for these events it is enough to upper bound

$$ \frac{1}{dt} \mathbb{E}[M_{\tilde{t}}(t + dt) - M_{\tilde{t}}(t)|\mathfrak{F}_t], $$

where it is important to bear in mind that $M_{\tilde{t}}(t + dt)$ stands for the collective score at time $t + dt$ of the vertices that belonged to the connected component at time $t$ (the connected component might have changed at time $t + dt$). As with (89), the expression above corresponds to a large sum of terms, which we group depending on the type of event they originate from:
• *Infections and recoveries within $\tilde{t}$.* In this contribution we bound the average infinitesimal changes in score due to the recoveries of vertices in $\tilde{t}$, as well as the infections between these vertices. Notice that this must take into account the possible reveal of new neighbours as a result of infecting a previously non visited vertex (following Rule (6)). Fix $j \in \tilde{t}$ with $j$ infected, and consider the following events:

- $j$ recovers. This event occurs at rate 1, and it results in the exclusion of $M_j$ from $M_{\tilde{t}}$ (all other terms remain unchanged). It follows that this event yields a total contribution

$$ - \sum_{i \in \tilde{t}} \tilde{s}_i(2\lambda)^{d(i,j)}. \qquad (91) $$

- $j$ infects an already visited neighbour $j' \in \tilde{t}$. This event results in the inclusion of $M_{j'}$ into $M_{\tilde{t}}$, while all other terms remain unchanged. Since for each $j' \sim j$, this occurs at rate $\lambda$, the event results in the total contribution

$$ \lambda \sum_{\substack{j' \sim j \\ j' \text{ visited}}} \sum_{i \in \tilde{t}} \tilde{s}_i(2\lambda)^{d(i,j')}. \qquad (92) $$

- $j$ infects a pending leaf $j' \in \tilde{t}$. This is the most delicate event, since it has the added effect of changing the value of $\tilde{s}_{j'}$ and connecting new vertices to $\tilde{t}$. We break down the changes in score as follows:

* For every $k \in \tilde{t}$, the change in value of $\tilde{s}_{j'}$ implies a decrease of $M_k$ by $\frac{2}{c-2}s_{j'}(2\lambda)^{d(k,j')}$. * For every $k \in \tilde{t}$, the connection of a vertex $l$ to $j'$ implies an increase of $M_k$ by

$$ \tilde{s}_l(2\lambda)^{d(k,l)} = \frac{2\lambda c}{c-2} s_l(2\lambda)^{d(k,j')} $$

where we have used that $d(k,l) = d(k,j') + 1$ and the fact that $l$ is not visited (for the definition of $\tilde{s}_l$).

* Since every weak vertex $l \notin G_t$ becomes a neighbour of $j'$ with probability $p_{j',l}$, it follows that the average change of $M_k$ is upper bounded by

$$ -\frac{2}{c-2}s_{j'}(2\lambda)^{d(k,j')} + \frac{2}{c-2}(2\lambda)^{d(k,j')} \sum_{l \text{ weak}} \lambda c p_{j',l} s_l \le 0 $$

where we have used (48) to deduce that $\sum \lambda c p_{j',l} s_l \le s_{j'}$.

Since the effect of revealing new vertices decreases all the $M_k$ in average, it follows that the change of $M_{\tilde{t}}$ by infecting a pending leaf can be upper bounded by the one given by the infection of an already visited vertex. We conclude that the total contribution is bounded by

$$ \lambda \sum_{\substack{j' \sim j \\ j' \text{ non visited}}} \sum_{i \in \tilde{t}} \tilde{s}_i(2\lambda)^{d(i,j')}. \qquad (93) $$

• *Network dynamics.* In this contribution we upper bound the average changes of $M_{\tilde{t}}$ that follow from the updates of weak vertices (not necessarily in $\tilde{t}$). Observe that on these events the infection does not spread so $M_{\tilde{t}}$ does not increase by adding new terms $M_j$, but
rather by modifying the values $M_i$ of all currently infected vertices in $\tilde{\mathfrak{t}}$. Fix then any such infected $i$ and observe that as long as $t+dt < T_{\text{bad}}$, the updating of another $i' \in \mathfrak{t}$ can only decrease $M_i$ (because the connected component of $i$ in $\mathfrak{t}$ is reduced) and hence the only transitions of the network that may increase $M_i(t)$ are:

* the update of $i$, or

* the update of an unseen vertex $k$ that then connects to some visited vertex $j \in \tilde{\mathfrak{t}}$, becoming a pending leaf.

In the first case, the resulting tree $\mathfrak{t}_i(t+dt)$ containing $i$ will just consist of $i$ and some pending leaves $j$. The average value of $M_i(t+dt)$ will then be

$$M_i(t+dt) \le s_i + \sum_{j \text{ weak}} \frac{2\lambda c}{c-2} p_{i,j} s_j \le s_i + \frac{2}{c-2} s_i = \frac{c}{c-2} s_i \quad (94)$$

where in the second inequality we have used (48). In the second case, the unseen vertex $k$ that connects to $j \in \tilde{\mathfrak{t}}$ will add to $M_i$ the quantity $(2\lambda)^{d(i,j)+1} \frac{c}{c-2} s_k$. Since the update of $i$ occurs at rate $\kappa_i \le \kappa_0$, and each $k$ attaches to a visited vertex $j$ with rate $\kappa_k p_{j,k} \le \kappa_0 p_{j,k}$ we deduce that the average change of $M_i$ due to these events is upper bounded by

$$\begin{aligned} & \kappa_0 \left( \frac{c}{c-2} s_i - M_i(t) \right) + \sum_{j \in \tilde{\mathfrak{t}}} \sum_k \kappa_0 p_{j,k} (2\lambda)^{d(i,j)+1} \frac{c}{c-2} s_k \\ & \le \kappa_0 \left( \frac{c}{c-2} M_i - M_i \right) + \sum_{j \in \tilde{\mathfrak{t}}} \frac{2\kappa_0}{c-2} (2\lambda)^{d(i,j)} s_j = \frac{4\kappa_0}{c-2} M_i, \end{aligned}$$

where we have used that $s_i \le M_i$ (since $i$ is infected), as well as (48), and in the equality we have used the definition of $M_i$. Adding all these average changes, and taking $c$ sufficiently large we obtain that the total contribution given by network dynamics events is

$$\sum_{\substack{i \in \tilde{\mathfrak{t}} \\ i \text{ infected}}} \frac{4\kappa_0}{c-2} M_i \le \frac{1}{8} M_{\tilde{\mathfrak{t}}}. \quad (95)$$

By adding the terms in (91), (92), and (93), for all infected vertices $j \in \tilde{\mathfrak{t}}$, as well as the contribution obtained in (95), we obtain that the expressions appearing in $\frac{1}{dt}\mathbb{E}[M_{\tilde{\mathfrak{t}}}(t+dt) - M_{\tilde{\mathfrak{t}}}(t)|\mathfrak{F}_t]$ can be upper bounded by

$$\begin{aligned} & \sum_{\substack{j \in \tilde{\mathfrak{t}} \\ j \text{ infected}}} \sum_{i \in \tilde{\mathfrak{t}}} \tilde{s}_i \left( \sum_{j' \sim j} \lambda(2\lambda)^{d(i,j')} - (2\lambda)^{d(i,j)} \right) + \frac{1}{8} M_{\tilde{\mathfrak{t}}} \\ & \le \sum_{\substack{j \in \tilde{\mathfrak{t}} \\ j \text{ infected}}} \sum_{i \in \tilde{\mathfrak{t}}} \tilde{s}_i \left( \lambda(2\lambda)^{d(i,j)-1} + \frac{1}{8\lambda^2} (2\lambda)^{d(i,j)+1} - (2\lambda)^{d(i,j)} \right) + \frac{1}{8} M_{\tilde{\mathfrak{t}}} \end{aligned}$$
$$ = -\frac{1}{4} \sum_{\substack{j \in \tilde{t} \\ j \text{ infected}}} \sum_{i \in \tilde{t}} \tilde{s}_i (2\lambda)^{d(i,j)} + \frac{1}{8} M_{\tilde{t}} = -\frac{1}{8} M_{\tilde{t}}, $$

where in the inequality we have used that for any pair of vertices $i, j \in t$, there is at most one vertex $j' \sim j$ satisfying $d(i, j') = d(i, j) - 1$, while the rest of the (at most) $\frac{1}{8\lambda^2}$ neighbours of $j$ satisfy $d(i, j') = d(i, j) + 1$.

Now that we have shown that the events involving vertices in $\tilde{t}$ and their interactions with other weak vertices induce an average change of at most $-\frac{1}{8}M_{\tilde{t}}$ in $M_{\text{weak}}$, we can consider all events involving only weak vertices (such that $t + dt < T_{\text{bad}}$) by adding all these contributions to obtain that their contribution to (90) is upper bounded by

$$ -\frac{1}{8} M_{\text{weak}}(t). $$

Similarly, it can be shown that the contribution of said events to

$$ \frac{1}{dt} \mathbb{E}[M_{t_j(t+dt)}(t+dt) - M_{t_j(t)}(t)|\mathfrak{F}_t] $$

is upper bounded by $-\frac{1}{8}M_{t_j(t)}(t)$. Indeed, we can repeat the exact same computations as for $M_{\tilde{t}}$, with the only exception of the case in which a vertex $j' \neq j$ in $t_j$ updates, which then becomes detached from $j$. We exploit this upper bound, together with the fact that for each strong vertex $i$, its scoring depends on the weak vertices only through the terms $R_{ij}$, which depend linearly on the corresponding $M_{t_j}$ to finally conclude that the contribution of events involving only weak vertices to the average change in the total score $M(t)$ is upper bounded by

$$ -\frac{1}{8} \sum_{\substack{i \text{ weak} \\ \text{infected}}} M_i(t) + \sum_{\substack{i \text{ strong} \\ \text{infected} \\ \text{unsaturated}}} -\frac{4}{8} R_i^{\text{weak}}(t) t_i + \sum_{\substack{i \text{ strong} \\ \text{healthy}}} -\frac{2}{8} R_i^{\text{weak}}(t) (s_i + t_i). \quad (96) $$

### (ii) Contributions from events that only involve strong vertices.

Observe that events only involving strong vertices do not affect $M_{\text{weak}}$. Indeed, the scoring of each $M_i$ depends on $t_i$ which is unaffected by these events, while the possible revealing of new weak vertices (as neighbours of strong ones) also leave $M_{\text{weak}}$ unaffected, since these new vertices are healthy. It follows that the events involving exclusively strong vertices only impact $M_{\text{strong}}$.

Noting the inherited rules concerning strong vertices, the almost identical score function to the one in the proof of Theorem 3, as well as the bonds (86), (87), and (88), it follows that the computations arising from these events are analogous to the ones in the previous proof, so we refrain from repeating them, although we point out that:

* When vertices update, the already revealed edges turn absent instead of unrevealed. This does not affect our computations since we always use worst-case scenario bounds. This actually improves some of the negative terms.
* The contributions obtained in (70) and (72), which depended on clear edges, now depend on present edges $(i, j)$ where both $i$ and $j$ are strong, but where at least one of them is strong quick. The term $N_i^{cl}(t)$ appearing in both terms is now replaced by the number of all such edges incident to $i$.

* The contribution computed in (71) still relates to the event in which an infected unsaturated strong slow vertex updates, thus revealing new neighbours. In that case only new strong slow neighbours affect the scoring.

* The contribution computed in (73) now relates to the transmission of the infection through a strong slow edge.

Following the same computations leading to (77) we obtain a total contribution of

$$ - \sum_{i \text{ infected unsaturated}} \left( 4r - \frac{17}{3} - \frac{4r}{3c} \right) \frac{s_i}{8r} - \sum_{i \text{ infected saturated}} \left( \frac{1}{3} - \frac{4r}{3c} \right) \kappa_i t_i - \sum_{\substack{i \text{ healthy} \\ \text{strong}}} \lambda N_i^{\text{sq}}(t) (s_i + t_i) - \sum_{\substack{(i,j) \text{ present} \\ \text{strong slow}}} \frac{2}{3} (\kappa_i + \kappa_j) (s_j + t_j + u_j), \quad (97) $$

where $N_i^{\text{sq}}$ is the number of non strong slow present edges connecting $i$ to strong vertices.

### (iii) Contributions from events that involve both strong and weak vertices.

The remaining transitions to consider are events that follow from infections of weak vertices by strong ones, and vice-versa. Moreover, we emphasize that the infection of a strong vertex by a weak one along a clogged edge can also lead to infection and saturation of other strong vertices by the “long distance saturation” rule.

* *Infection of weak vertices by strong neighbours.* The infection of a weak vertex $j$ by a neighbouring strong infected vertex $i$ happens at rate $\lambda$. Following similar computations to the ones in (94), we deduce that $j$ increases its score in average by $M_j(t)$ (even if infecting $j$ resulted in revealing new neighbours). It follows that if $i$ is unsaturated, then it increases its score by at most $64\lambda M_j(t)t_i/s_j$. This yields the contribution

$$ \sum_{i \text{ strong infected unsaturated}} 64\lambda^2 \sum_{\substack{j \text{ weak} \\ \text{j healthy}}} \frac{M_j(t)}{s_j} t_i + \sum_{\substack{i \text{ strong} \\ \text{infected}}} \sum_{\substack{j \text{ weak} \\ \text{j healthy}}} \lambda M_j(t). \quad (98) $$

* *Infection of a strong healthy vertex by a connected weak vertex.* The infection of a strong vertex $i$ by a weak infected vertex $j$ through a present edge holds at rate $\lambda$, leading to the contribution

$$ \sum_{i \text{ strong healthy}} \sum_{j \text{ weak infected} \sim i} \lambda(s_i + t_i). $$

Observing that $j$ is infected, we have $M_{t_j} \ge s_j$ and thus $R_{ij}(t) \ge 16\lambda$, we can further bound this contribution by

$$ \sum_{i \text{ strong healthy}} \frac{R_i^{\text{weak}}(t)}{16} (s_i + t_i). \quad (99) $$
• *Infection of a strong healthy vertex by a weak one along a clogged edge.* The infection of a strong vertex *j* by a weak infected vertex *i* holds at rate $\lambda p_{ij}$ when the edge is clogged. Apart from a possible long distance effect, which is taken into account separately below, this transmission creates an average score associated to *j* and to the strong slow vertices pending to *j* (when *j* is slow) at most of

$$ (s_j + t_j) + u_j \leq \frac{4}{3}s_j. $$

Summing over *i* and *j* and using the inequality (48) available for the weak vertex *i*, we obtain a contribution bounded by

$$ \sum_{\substack{i \text{ weak} \\ \text{infected}}} \frac{4}{3c} s_i \le \sum_{\substack{i \text{ weak} \\ \text{infected}}} \frac{4}{3c} M_i(t). \qquad (100) $$

• *Long distance saturation.* For each strong unsaturated *i* and each weak neighbour *j* of *i*, a vertex *k* ∈ t_j may infect another strong vertex (through a clogged edge), leading to infection and saturation of *i*, and thus a score increase of at most t_i if *i* infected, or (s_i + t_i) + u_i if *i* healthy (taking into account the possible revealing of strong slow vertices pending to *i* in that case). For each such *i* and *j*, this holds at rate

$$ \sum_{\substack{k \in t_j \\ \text{infected}}} \sum_{i' \text{ strong}} \lambda p_{k,i'} \le \sum_{\substack{k \in t_j \\ \text{infected}}} \lambda \int_{x' < a_{\text{str}}} p\left(\frac{k}{N}, x'\right) dx' \le \frac{\lambda}{s(a_{\text{str}})} \sum_{\substack{k \in t_j \\ \text{infected}}} s_k \le \frac{\lambda M_{t_j}}{s_j} = \frac{R_{ij}}{16}, $$

where the third inequality follows from (H1) and the last inequality from the definition of $M_{t_j}$ and $s_j \le s(a_{\text{str}})$. Summing over the choices of *i* and *j*, we obtain a contribution bounded by

$$ \sum_{\substack{i \text{ strong infected} \\ \text{unsaturated}}} \frac{1}{16} R_i^{\text{weak}}(t) t_i + \sum_{\substack{i \text{ strong} \\ \text{healthy}}} \frac{1}{8} R_i^{\text{weak}}(t) s_i. \qquad (101) $$

### (iv) Total contribution.

Grouping the contributions obtained in (96), (97), (98), (99), (100), and (101), we can upper bound the infinitesimal increase of *M* as

$$ \frac{1}{dt} \mathbb{E}[(M(t + dt) - M(t)) | \mathfrak{F}_t] \\ \le \sum_{\substack{i \text{ weak} \\ \text{infected}}} I_i(t) + \sum_{\substack{i \text{ strong} \\ \text{pending}}} I_i^{\text{pend}}(t) + \sum_{\substack{i \text{ strong infected} \\ \text{unsaturated}}} I_i^{\text{inf}}(t) + \sum_{\substack{i \text{ strong} \\ \text{healthy}}} I_i^{\text{hea}}(t) + \sum_{\substack{i \text{ strong infected} \\ \text{saturated}}} I_i^{\text{sat}}(t), $$
where the expressions of the terms inside the sums are given by

$$I_i(t) = -\left(\frac{1}{8} - \frac{4}{3c}\right) M_i(t)$$

$$I_i^{\text{pend}}(t) = -\frac{2}{3}\kappa_i(s_i + t_i + u_i).$$

$$I_i^{\text{inf}}(t) = -\left(4r - \frac{17}{3} - \frac{4r}{3c}\right) \frac{s_i}{8r} + \sum_{j \text{ weak}\sim i} \lambda M_j(t) + 64\lambda^2 t_i \sum_{j \text{ weak}\sim i} \frac{M_j(t)}{s_j} - \frac{7}{16} R_i^{\text{weak}}(t) t_i,$$

$$I_i^{\text{hea}}(t) = -\left(\lambda N_i^{\text{sq}}(t) + \frac{1}{16} R_i^{\text{weak}}(t)\right) (s_i + t_i),$$

$$I_i^{\text{sat}}(t) = -\left(\frac{1}{3} - \frac{4r}{3c}\right) \kappa_i t_i + \sum_{j \text{ weak}\sim i} \lambda M_j(t).$$

Taking $r$ and $c$ large with still $c > 4r$, we have that the terms $\frac{1}{8} - \frac{4}{3c}$, $\frac{1}{3} - \frac{4r}{3c}$ and $4r - \frac{17}{3} - \frac{4r}{3c}$ are all positive, as well as $4r - 6 - \frac{4r}{3c}$. Define the expressions,

$$J_i(t) := \sum_{j \text{ weak}\sim i} \lambda M_j(t), \quad K_i(t) := \sum_{j \text{ weak}\sim i} \frac{M_j(t)}{s_j}$$

and note that as soon as there is some $\varepsilon > 0$ such that the inequalities

$$J_i(t) \le \left(\frac{1}{3} - \frac{4r}{3c} - \varepsilon\right) \kappa_i t_i, \quad (102)$$

$$K_i(t) \le \left(4r - 6 - \frac{4r}{3c} - \varepsilon\right) \frac{\pi_i}{32}, \quad (103)$$

hold, then (102) ensures that $I_i^{\text{sat}}(t) \le -\varepsilon\kappa_i t_i$ as well as

$$J_i(t) \le \frac{\kappa_i t_i}{3} = \frac{s_i}{3r T_i^{\text{loc}}} \le \frac{1}{3} \frac{s_i}{8r},$$

while (103) ensures that $64\lambda^2 t_i K_i(t) \le (4r - 6 - \frac{4r}{3c} - \varepsilon) \frac{s_i}{8r}$ and further $I_i^{\text{inf}}(t) \le -\varepsilon s_i / 8r$, so in particular all the contributions become negative. With this in mind we define at last the missing stopping time $T_{\text{bad}}^{\text{conn}}$ as

$$T_{\text{bad}}^{\text{conn}} = \inf \left\{ t \ge 0, \begin{array}{l} (102) \text{ or } (103) \text{ fails to hold for at least} \\ \text{one vertex } i \text{ amongst the visited strong vertices} \end{array} \right\}, \quad (104)$$

for some values of $r$, $c$ and $\varepsilon > 0$ that are still not fixed, but satisfy all previously mentioned constraints. We then have:

$$\frac{1}{dt} \mathbb{E}[M_{t+dt} - M_t | \mathfrak{F}_t] \le -c_{(105)} \mathbf{1}_{t<T}, \quad (105)$$

for some $c_{(105)} > 0$ independent of $i_0$, $t$, and $N$. We therefore conclude that both $(M(t \wedge T))_{t \ge 0}$ and $(M(t \wedge T) + c_{(105)}(t \wedge T))_{t \ge 0}$ are supermartingales.

**Exploiting the supermartingale.** As in the previous proof, our aim is to exploit the supermartingale property to prove Theorem 4. First, we bound $\mathbb{P}_i(t < T_{\text{ext}})$ as follows:

$$\begin{aligned} \mathbb{P}_i(t < T_{\text{ext}}) &\le \mathbb{P}_i(t \le T) + \mathbb{P}_i(T = T_{\text{hit}}) + \mathbb{P}_i(t \le T_{\text{ext}}, T < t, T \ne T_{\text{hit}}) \\ &\le \mathbb{P}_i(t \le T) + \mathbb{P}_i(T = T_{\text{hit}}) + \mathbb{P}_i(T_{\text{bad}} < T_{\text{hit}} \wedge t). \end{aligned}$$
As in the previous proof, $M(0)$ is not deterministic under $\mathbb{P}_i$ but satisfies $s_i \le \mathbb{E}_i[M(0)] \le \frac{7}{6}s_i$, so the optional stopping theorem applied to $M(\cdot \wedge T)$ implies $\mathbb{P}_i(T = T_{\text{hit}}) \le \frac{7s_i}{6s(a)}$. Moreover, with the optional stopping theorem applied to $M(\cdot \wedge T) + c_{(105)}(\cdot \wedge T)$, we get

$$ \mathbb{P}_i(t < T) \le \frac{1}{t} \mathbb{E}_i[T] \le \frac{1}{c_{(105)}t} \mathbb{E}_i[M_0] \le \frac{7s_i}{6c_{(105)}t}. $$

Using (78), we now obtain

$$ I_N(t) \le a + \frac{1}{N} + \frac{7}{6} \left( \frac{1}{s(a)} + \frac{1}{c_{(105)}t} \right) \int_a^1 s(y)dy + \frac{1}{N} \sum_{i=[aN]+1}^{N} \mathbb{P}_i(T_{\text{bad}} < T_{\text{hit}} \wedge t_0). \quad (106) $$

This expression resembles (53), except for the last term. In Subsection 5.3, we will prove that we can bound this term at time $t = t_0 := 7s(a)/c_{(105)}$ as

$$ \frac{1}{N} \sum_{i=[aN]+1}^{N} \mathbb{P}_i(T_{\text{bad}} < T_{\text{hit}} \wedge t_0) \le a + \frac{\omega'}{N}, \quad (107) $$

for some choice of $\omega' = \omega'(\lambda)$, and small $\lambda$. Taking this for granted, we continue as follows:

* For $t \le t_0$, we bound $\mathbb{P}_i(T_{\text{bad}} < T_{\text{hit}} \wedge t)$ by $\mathbb{P}_i(T_{\text{bad}} < T_{\text{hit}} \wedge t_0)$ to obtain

$$ I_N(t) \le 2a + \frac{7}{6s(a)} \int_a^1 s(y)dy + \frac{\omega}{t} + \frac{1+\omega'}{N}, $$

$$ \text{with } \omega = \omega(\lambda) = \frac{7}{6c_{(105)}} \int_a^1 s(y)dy. $$

* For $t \ge t_0$, we use that $I_N$ is nonincreasing to bound $I_N(t)$ by $I_N(t_0)$, which, using again (107) and the equality $\frac{7}{6}(\frac{1}{s(a)} + \frac{1}{c_{(105)}t_0}) = \frac{4}{3s(a)}$, yields

$$ I_N(t) \le 2a + \frac{4}{3s(a)} \int_a^1 s(y)dy + \frac{1+\omega'(\lambda)}{N}. $$

Thus (53) is satisfied for all $t \ge 0$, showing Theorem 4. It only remains to prove (107).

### 5.3. Bound on the probability of stopping the exploration early.
We will provide a bound of the form

$$ \mathbb{P}_i(T_{\text{bad}} < T_{\text{hit}} \wedge t_0) \le o(a(\lambda)) + \frac{\omega'(\lambda)}{N}, \quad (108) $$

valid for all small $\lambda$ and large $N$, and uniformly over $i \in \{\lceilaN\rceil + 1, \dots, N\}$, from which (107) naturally follows. Recall the definition of $t_0 = t_0(\lambda) = 7s(a)/c_{(105)}$ and $T_{\text{bad}} = T_{\text{tree}}^{\text{deg}} \wedge T_{\text{bad}}^{\text{deg}} \wedge T_{\text{bad}}^{\text{conn}}$, and introduce further the following stopping times:

* $T_\ell$, for $\ell \ge 1$, the time of the $\ell$-th infection, where an infection means a vertex transitioning from the state healthy to infected (and possibly saturated). Note that two infections can occur simultaneously (by the saturation rules (8)(i) or (8)(ii)), in which case we count the two infections, so we might have $T_\ell = T_{\ell+1}$ for example. A single vertex can also be infected multiple times. In any case, we can roughly bound the number of visited vertices at times $t < T_\ell$ by $\ell$.
• $\tilde{T}_{\text{deg}}$, the smallest time when a visited strong vertex is connected to more than $2c_2a^{-\gamma}$ weak vertices in $G_t$. Note that when incorporated to the network, a strong vertex $j$ was possibly connected to a weak vertex $i$ that has infected it (so that $(i, j)$ has been incorporated to $G_t$). However, its connections to the other weak vertices follow the same dynamics as in the original stationary dynamic network (by rules (6) and (7)). It follows that at any given time $t$, we can use (1) to bound the average number of present weak edges $(j, k)$ by $c_2a^{-\gamma}$. Being connected to more than $2c_2a^{-\gamma}$ is thus an unlikely event, which will help us to control the more involved quantities $J_j(t)$ and $K_j(t)$ appearing in (102) and (103).

We have

$$ \begin{aligned} \mathbb{P}_i(T_{\text{bad}} < T_{\text{hit}} \wedge t_0) &\le \mathbb{P}_i(T_\ell \wedge T_{\text{bad}}^{\text{tree}} \wedge T_{\text{bad}}^{\text{deg}} \wedge \tilde{T}_{\text{deg}} \wedge T_{\text{bad}}^{\text{conn}} < T_{\text{hit}} \wedge t_0) \\ &\le P^{\text{infected}} + P^{\text{tree}} + P^{\text{deg}} + P^{\text{conn}}, \end{aligned} $$

where the second line is obtained by looking at which of the stopping times is smallest, and the terms are defined as

$$ P^{\text{infected}} := \mathbb{P}_i(T_\ell \le T_{\text{bad}} \wedge T_{\text{hit}} \wedge t_0), $$

$$ P^{\text{tree}} := \mathbb{P}_i(T_{\text{bad}}^{\text{tree}} < T_\ell \wedge T_{\text{hit}} \wedge t_0), $$

$$ P^{\text{deg}} := \mathbb{P}_i(T_{\text{bad}}^{\text{deg}} \wedge \tilde{T}_{\text{deg}} < T_\ell \wedge T_{\text{bad}}^{\text{tree}} \wedge T_{\text{hit}} \wedge t_0), $$

$$ P^{\text{conn}} := \mathbb{P}_i(T_{\text{bad}}^{\text{conn}} < T_\ell \wedge T_{\text{bad}}^{\text{tree}} \wedge T_{\text{bad}}^{\text{deg}} \wedge \tilde{T}_{\text{deg}} \wedge T_{\text{hit}} \wedge t_0). $$

We now prove that

$$ \begin{aligned} P^{\text{tree}} &\le \frac{\omega'(\lambda)}{N}, \\ P^{\text{infected}} + P^{\text{deg}} + P^{\text{conn}} &= o(a(\lambda)), \end{aligned} $$

when $\ell$ is chosen as

$$ \ell = \ell(\lambda) = \lambda^{-C_{(109)}} \qquad (109) $$

with $C_{(109)} > 0$ defined below.

**Bounding the total number of infections.** We prove

$$ P^{\text{infected}} \le \frac{2 + 4s(a)^2}{\ell}. \qquad (110) $$

From now on, we fix a sufficiently large value of $C_{(109)}$ to ensure this is $o(a)$. This is possible as $a^{-1}$ and $s(a(\lambda))$ are growing polynomially in $\lambda^{-1}$.

*Proof.* The idea is to associate each infection with a positive increase of value at least $1/2$ for the supermartingale $M(t \wedge T)$, and then use standard martingale theory to obtain the desired upper bound. Indeed, the infection of a weak vertex $i$ implies a score increase of at least $s_i \ge 1$, while the infection of a strong vertex $i$ implies an increase of its associated score $m_i$ of at least $s_i/2 \ge 1/2$. This simple idea however has to take into consideration several subtleties.
* The infection of a strong pending vertex possibly implies a *decay of the total score*. This is due to the fact that while the vertex becomes infected (and saturated), the edge simultaneously also becomes saturated, which implies a decay of its associated score. For this reason, in this proof, we will consider a strong pending vertex as already infected when counting the number of “infections”.

* By the previous consideration, when a strong vertex $i$ reveals a strong pending leaf $j$, we count this as an infection, which we also want to associate to an increase of score. However, it might be the case that $i$ was itself a strong pending leaf, that was just infected by another strong slow edge $(k, i)$. In that case, the following events occur simultaneously:

- $i$ gets infected and saturated, with associated score $s_i + t_i$.

- $k$ also gets saturated (if it were not before), but for simplicity we neglect this effect from this discussion.

- The edge $(k, i)$ becomes saturated, implying a score decrease of $s_i + t_i + u_i$. These first events together thus imply possibly a score decrease of $u_i$.

- The vertex $i$ has revealed the pending strong slow vertex $j$ (and possibly other strong slow and weak vertices as well). The increase in score associated to this newly revealed strong slow vertex is $s_j + t_j + u_j$.

The problem is that the increase $s_j + t_j + u_j$ might be compensated by the decrease $u_i$, so it is not clear whether we can associate a score increase to the revelation of $j$.

In order to overcome this difficulty, we define a discrete-time supermartingale $(M_n^{\text{disc}})_{n \ge 0}$, that evolves as the jump process associated to the supermartingale $M_t$, except for the particular case in which a strong slow vertex $i$ is infected by another strong slow vertex $k$. In that case, the discrete-time process $M^{\text{disc}}$ decomposes the jump $\Delta M_t$ into several jumps as follows:

* As a first jump of $M^{\text{disc}}$, it increases due to the change in score given by the saturation of $i$, $k$, and $(k, i)$, the revelation of new weak neighbours of $i$, and an additional term $\sum_j \text{strong slow } p_{ij}(s_j + t_j + u)$ representing the average increase of $M_t$ resulting from the revelation of new strong slow neighbours. Equivalently, this term can be seen as the result of assigning a temporary score $p_{i,j}(s_j + t_j + u_j)$ to each strong slow edge $(i, j)$, before attempting to reveal it as in Rule (3).

* For the remaining steps associated to this event, we successively attempt to reveal each strong slow edge $(i, j)$ (starting from the smallest $j$ or in other arbitrary order), and replace the score $p_{i,j}(s_j + t_j + u_j)$ by either $(s_j + t_j + u_j)$ or 0, according to whether the edge was revealed or not.

Once the vertex $i$ has gone through all the strong slow vertices, the two processes coincide again (via a time-change that we do not write down explicitly). This provides the construction of $(M_n^{\text{disc}})_{n \ge 0}$. Note that:

* When we successfully reveal a strong slow neighbour $j$, this implies a positive jump $\Delta M_n^{\text{disc}} = (1 - p_{i,j})(s_j + t_j + u_j) \ge 1/2$, using that $p_{i,j} \le p(a, a)/N \le 1/2$ for large $N$. Actually it is now true that any “infection” that we count in this proof is associated to an increase $\Delta M_n^{\text{disc}} \ge 1/2$. We might also have two simultaneous infections, or reveal
several strong pending vertices when a strong slow vertex updates, but in each case the total number of simultaneous “infections” is bounded by $2\Delta M_n^{\text{disc}}$.

* The first jump of $M^{\text{disc}}$ is on average equal to $\Delta M_t$, while the rest of the jumps have mean 0. Doing this, we maintain the supermartingale property of the process, so $M^{\text{disc}}$ is indeed a supermartingale.

* The process $M^{\text{disc}}$ takes nonnegative values, and it can reach a value larger than $s(a)$ only at a moment corresponding to the time $T_{\text{hit}}$ when $M_t$ also reaches such a value.

Writing $N_{\text{hit}} := \inf\{n \ge 0, M_n^{\text{disc}} > s(a)\}$ and $Z_n := (s(a) - M_{n \wedge N_{\text{hit}}}^{\text{disc}})_+$, we have that $Z_n$ is a submartingale with values in $[0, s(a)]$. The total number of infections occurring before time $T$ can now be bounded (using also $T \le T_{\text{hit}}$), by

$$ \sum_{n < N_{\text{hit}}} 2\Delta M_n^{\text{disc}} \mathbf{1}_{\Delta M_n^{\text{disc}} \ge 1/2} \le 4 \sum_{n < N_{\text{hit}}} (\Delta M_n^{\text{disc}})^2. $$

Noting that we have $\Delta Z_n = -\Delta M_n^{\text{disc}}$ for $n < N_{\text{hit}}$, we can further bound the expected number of infections occurring before time $T$ by

$$ 4\mathbb{E}\left[\sum_{n < N_{\text{hit}}} (\Delta Z_n)^2\right] \le 4\mathbb{E}[Z_{\infty}^2 - Z_0^2] \le 4s(a)^2. $$

We also have at most two additional infections occurring at time $T$. Then (110) follows by the Markov inequality. □

**Bounding the probability of breaking the tree structure.** We now prove

$$ P^{\text{tree}} \le 8\ell^2(2\kappa_0 t_0 + \lambda t_0 + \ell + 1)^2 \frac{p(a, a)^2}{N} =: \frac{\omega'(\lambda)}{N}. $$

*Proof.* Introduce, in this proof only, the notation $\tilde{T} := T_k \wedge T_{\text{hit}} \wedge t_0$, and the quantities

$$ E_{\text{rep}}^{\text{tree}} = \left\{ \begin{array}{l} (i, j) \in \{1, 2, \dots, N\}^2, \text{ such that } (i, j) \text{ becomes present at} \\ \text{least twice before time } \tilde{T} \end{array} \right\} $$

$$ V_{\text{cycle}}^{\text{tree}} = \left\{ \begin{array}{l} j \in \{1, 2, \dots, N\}, \text{ there are } i, i' \in \{1, 2, \dots, N\} \text{ such that} \\ \text{both } (i, j) \text{ and } (i', j) \text{ become present before time } \tilde{T} \end{array} \right\} $$

It follows that $T_{\text{bad}}^{\text{tree}} < \tilde{T}$ if and only if $|E_{\text{rep}}^{\text{tree}}| + |V_{\text{cycle}}^{\text{tree}}| \ge 1$ so from the Markov inequality, we can bound

$$ P^{\text{tree}} \le \mathbb{E}[|E_{\text{rep}}^{\text{tree}}|] + \mathbb{E}[|V_{\text{cycle}}^{\text{tree}}|]. $$

The quantities in both expectations involve counting edges that become present, so we stress that in order for an edge $(i, j)$ to become present at time $t < \tilde{T}$:

* The edge $i$ must be visited at time $t$.

* It must be the case that at time $t$ either:

- $(i, j)$ is a strong quick edge and $i$ is infecting $j$ (which was previously not in the network), or

- $i$ or $j$ updates, or

- $i$ is a strong slow neighbour which becomes saturated due to Rule (8.iii).
Denote by $\tau_i$ the time at which vertex $i$ becomes visited, and $N_{\text{visited}}$ the number of visited vertices by time $\tilde{T}$. We now bound $|E_{\text{rep}}^{\text{tree}}|$ and $|V_{\text{cycle}}^{\text{tree}}|$ separately:

• Repeated edges: Start from the observation

$$ \mathbb{E}[|E_{\text{rep}}^{\text{tree}}|] = \sum_{\text{edges } (i,j)} \mathbb{P}(\tau_i < \tilde{T} \text{ and } (i,j) \text{ becomes present at least twice before time } \tilde{T}) $$

and observe that, conditionally on $\tau_i$:

- The number of updates of $(i, j)$ in $(\tau_i, \tilde{T}]$ that result in the edge being present is bounded by an independent Poisson random variable with rate $(\kappa_i+\kappa_j)(\tilde{T}-\tau_i)p_{i,j} \le 2\kappa_0t_0p_{i,j}$.

- Since $\tilde{T} \le T_\ell$, there are at most $\ell$ infections within $[\tau_i, \tilde{T}]$ which could reveal $(i, j)$ due to Rule (8.iii), and at each such infection an independent coin with probability $p_{i,j}$ is tossed to decide whether the edge becomes present.

- The number of possible events in which $(i, j)$ is infecting $j$ through a clogged edge is bounded by a Poisson random variable with rate $\lambda t_0 p_{i,j}$.

We thus deduce that, conditionally on $\tau_i$, the probability of $(i, j)$ becoming present at least twice is bounded by

$$ 2(2\kappa_0t_0 + \lambda t_0 + \ell + 1)^2 p_{i,j}^2 \le 2(2\kappa_0t_0 + \lambda t_0 + \ell + 1)^2 \frac{p(a, a)^2}{N^2}, $$

and as there are at most $\ell$ infections before time $\tilde{T}$, it must be that $N_{\text{visited}} \le \ell$, so

$$ \begin{aligned} \mathbb{E}[|E_{\text{rep}}^{\text{tree}}|] &\le \sum_{\text{edges } (i,j)} \mathbb{P}(\tau_i < \tilde{T}) 2(2\kappa_0t_0 + \lambda t_0 + \ell + 1)^2 \frac{p(a, a)^2}{N^2} \\ &= \sum_{i=1}^N \mathbb{P}(\tau_i < \tilde{T}) 2(2\kappa_0t_0 + \lambda t_0 + \ell + 1)^2 \frac{p(a, a)^2}{N} \\ &\le 2\ell(2\kappa_0t_0 + \lambda t_0 + \ell + 1)^2 \frac{p(a, a)^2}{N} \end{aligned} $$

• Cycles: This case is similar to the previous one, where we can write

$$ \mathbb{E}[|V_{\text{cycle}}^{\text{tree}}|] = \sum_{i,j,l} \mathbb{P}(\tau_i, \tau_j < \tilde{T}, \text{ and both } (i,l) \text{ and } (j,l) \text{ become present before time } \tilde{T}). $$

Following the same line of thought as in the previous case, we deduce that, conditionally on $\tau_i$ and $\tau_j$, the probability of both $(i, l)$ and $(j, l)$ becoming present is bounded by

$$ 4(2\kappa_0t_0 + \lambda t_0 + \ell + 1)^2 p_{i,l}p_{j,l} \le 4(2\kappa_0t_0 + \lambda t_0 + \ell + 1)^2 \frac{p(a, a)^2}{N^2}, $$
and hence we obtain

$$
\begin{align*}
\mathbb{E}[|V_{\text{cycle}}^{\text{tree}}|] &\le \sum_{i,j,l} \mathbb{P}(\tau_i, \tau_j < \tilde{T}) 4(2\kappa_0 t_0 + \lambda t_0 + \ell + 1)^2 \frac{p(a, a)^2}{N^2} \\
&= \sum_{i,j} \mathbb{P}(\tau_i, \tau_j < \tilde{T}) 4(2\kappa_0 t_0 + \lambda t_0 + \ell + 1)^2 \frac{p(a, a)^2}{N} \\
&\le 4\ell^2 (2\kappa_0 t_0 + \lambda t_0 + \ell + 1)^2 \frac{p(a, a)^2}{N}.
\end{align*}
$$

The conclusion follows by adding both bounds. □

**Bounding the degrees.** We prove below the upper bounds

$$
P^{\deg} \leq \ell t_0 e^{-c_{(111)} \lambda^{-2}}, \qquad (111)
$$

with $c_{(111)} > 0$ a constant independent of $\lambda$ or $N$. As $\ell$ and $t_0$ are polynomial in $\lambda$, this
term is exponentially small in $\lambda$, and in particular negligible compared to $a$ as $\lambda \to 0$.

Proof. At times $t < T_{\text{bad}}^{\text{tree}}$, each vertex $j$ in $G_t$ (except $i_0$) is the head of one edge $(i,j) \in G_t$, with possibly $i$ weak. Once $j$ is infected, every other weak edge $(j,k)$ is revealed and evolves as in the true stationary dynamic network. Therefore, conditionally given $j$ is in $G_t$, the number $N_j^w(t)$ of present weak edges $(j,k)$ in $G_t$, follows a Poisson binomial distribution, with expectation bounded by $1/10\lambda^2$ if $j$ is itself a weak vertex. Therefore, for given $t$, the probability of having $N_j^w(t) \ge 1/9\lambda^2$ is uniformly bounded by $e^{-c\lambda^{-2}}$ for some constant $c > 0$. Moreover, the updating rates of the vertices are upper bounded, therefore one can define a time step $\tau$ such that for any given $s$,

$$
\mathbb{P} \left( \min \{ N_j^w(u) : s \le u \le s + \tau \} \ge \frac{1}{9\lambda^2} \mid N_j^w(s) \ge \frac{1}{8\lambda^2} \right) \ge \frac{1}{2}.
$$

It follows that we have

$$
\mathbb{P} \left( \max\{N_j^w(s): s \le t\} \ge \frac{1}{8\lambda^2} \mid j \in G_t \right) \le \frac{2t}{\tau} e^{-c\lambda^{-2}}.
$$

Now, we inspect the successively infected weak vertices one by one up until time $T_\ell \wedge T_{\text{bad}}^{\text{tree}} \wedge T_{\text{hit}} \wedge t_0$. We find at most $\ell$ such vertices, for which we can use the previous bound with $t = t_0$. Thus the probability of finding a weak vertex with at least $1 + \lfloor 1/8\lambda^2 \rfloor$ weak neighbours is bounded by $\frac{2\ell t_0}{\tau} e^{-c\lambda^{-2}}$. Similarly, for a strong vertex $j > aN$ and conditionally given $j \in G_t$, the number of present weak edges $(j,k)$ in $G_t$ follows a Poisson binomial distribution with expectation bounded by $c_2 a^{-\gamma}$, and we deduce that the probability of finding a strong vertex connected to more than $2c_2 a^{-\gamma}$ weak vertices is also bounded by $\frac{2\ell t_0}{\tau} e^{-c\lambda^{-2}}$ (with a possibly different value of $c > 0$). We deduce (111) by decreasing the value of $c > 0$ if necessary. $\square$
**Bounding the connectivities of visited strong vertices.** It finally remains to bound the probability $P^{conn}$ to visit a strong vertex $i$ that fails to satisfy (102) or (103) by having a too large value for $J_i(t)$ or $K_i(t)$. This last bound is more technical than the previous ones, and before tackling it, we first provide an upper bound for quantities that can be thought of at upper bounds for $J_i(t)$ and $K_i(t)$ in a fixed idealized environment.

**A large deviation upper bound in an idealized environment.** Fix a strong vertex $i$, and introduce a family $(C_{j_1, \dots, j_n})_{n \ge 1, j_1, \dots, j_n \text{ weak}}$ of independent random variables, indexed by the sequences of distinct weak vertices, such that $C_{j_1}$ is Bernoulli distributed with parameter $p_{i, j_1}$ and, for $n \ge 2$, $C_{j_1, \dots, j_n}$ is Bernoulli distributed with parameter $p_{j_{n-1}, j_n}$. Define

$$ \bar{J}_i = \sum_{j \text{ weak}} \lambda C_j \bar{M}_j, \quad \bar{K}_i = \sum_{j \text{ weak}} \frac{C_j}{s_j} \bar{M}_j, $$

where $\bar{M}_j$ is defined by

$$ \bar{M}_j := 2s_j + 2 \sum_{n \ge 1} \sum_{j_1, \dots, j_n \text{ weak}} \left( \prod_{k=1}^{n} 2\lambda C_{j, j_1, \dots, j_k} \right) s_{j_n}. $$

**Proposition 8.** For $c$ sufficiently large, there exists a finite constant $C_8$ such that the following results hold:

(1) for any $j$ weak and any $\theta \ge 0$ satisfying $\theta \le 1/(2\lambda s(a_{\text{str}}))$ and $\theta \le s_j^{-1}$, we have:

$$ \mathbb{E}[e^{\theta \bar{M}_j}] \le 1 + C_8 \theta s_j. $$

(2) for any $j$ weak and any $\theta \ge 0$ satisfying $\theta \le 1/(2\lambda s(a_{\text{str}}))$, we have

$$ \mathbb{E}[e^{\theta \bar{M}_j}] \le e^{C_8 \theta s_j}. $$

(3) for any $i$ strong and any $\theta \ge 0$ satisfying $\theta \le 1/(\lambda s(a_{\text{str}}))$, we have

$$ \mathbb{E}[e^{\theta \bar{J}_i}] \le e^{C_8 \theta \sigma_i} \le e^{\frac{C_8 \theta}{\epsilon} \frac{s_i}{T_i^{\text{loc}}}}, $$

$$ \text{where } \sigma_i = \lambda \sum_{j \text{ weak}} p_{ij} s_j. $$

(4) for any $i$ strong and any $\theta \ge 0$ satisfying $\theta \le 1$ and $\theta \le 1/(2\lambda s(a_{\text{str}}))$, we have

$$ \mathbb{E}[e^{\theta \bar{K}_i}] \le e^{\frac{C_8}{2\kappa_0} \theta \tilde{\sigma}_i} \le e^{C_8 \theta \pi_i}, $$

$$ \text{where } \tilde{\sigma}_i = \sum_{j \text{ weak}} p_{ij}. $$

**Proof of Proposition 8.** We focus on the first point of the proposition. For $j$ weak and $n \ge 0$, we introduce

$$ \bar{M}_j^{(n)} := 2s_j + 2 \sum_{k=1}^{n} \sum_{j_1, \dots, j_k \text{ weak}} \left( \prod_{l=1}^{k} 2\lambda C_{j, j_1, \dots, j_l} \right) s_{j_k}, $$
so that $\bar{M}_j^{(0)} = 2s_j$ and $\bar{M}_j = \lim \bar{M}_j^{(n)}$. We prove recursively on $n$ the existence of a constant $C_8 > 0$ independent of $n$ such that, for any $j$ weak and any $\theta \ge 0$ satisfying $\theta \le 1/(2\lambda s(a_{\text{str}}))$ and $\theta \le s_j^{-1}$, we have

$$ \mathbb{E}[e^{\theta \bar{M}_j^{(n)}}] \le 1 + C_8 \theta s_j. $$

For $n=0$, using the convexity of the exponential function and $\theta s_j \le 1$, we have

$$ e^{\theta \bar{M}_j^{(0)}} = e^{2\theta s_j} \le 1 + (e^2 - 1)\theta s_j, $$

whence the result holds if $C_8 \ge e^2 - 1$. For the induction step, write

$$ \bar{M}_j^{(n)} = 2s_j + \sum_{j_1 \text{ weak}} 2\lambda C_{j,j_1} \bar{M}_{j,j_1}^{(n)}, $$

where the random variables

$$ \bar{M}_{j,j_1}^{(n)} := 2s_{j_1} + 2 \sum_{k=2}^{n} \sum_{j_2, \dots, j_n} \left( \prod_{l=2}^{n} 2\lambda C_{j,j_1, \dots, j_l} \right) s_{j_k} $$

are independent, independent from the variables $C_{j,j_1}$, and have the same laws as $\bar{M}_{j_1}^{(n-1)}$. Further,

$$ \mathbb{E}[e^{\theta \bar{M}_j^{(n)}}] = e^{2\theta s_j} \prod_{j_1 \text{ weak}} \mathbb{E}[e^{2\lambda\theta C_{j,j_1} M_{j,j_1}^{(n)}}] = e^{2\theta s_j} \prod_{j_1 \text{ weak}} \left( 1 + p_{jj_1} \left( \mathbb{E}[e^{2\lambda\theta \bar{M}_{j_1}^{(n-1)}}] - 1 \right) \right). $$

From the hypothesis $\theta \le 1/(2\lambda s(a_{\text{str}}))$, it follows $2\lambda\theta \le 1/s(a_{\text{str}}) \le 1/s_{j_1}$ for all $j_1$ weak, as well as $2\lambda\theta \le \theta \le 1/(2\lambda s(a_{\text{str}}))$, since $\lambda \le 1/2$. We can thus apply the induction hypothesis to obtain

$$ \begin{aligned} \mathbb{E}[e^{\theta \bar{M}_j^{(n)}}] &\le e^{2\theta s_j} \prod_{j_1 \text{ weak}} (1 + 2\lambda\theta C_8 p_{jj_1} s_{j_1}) \\ &\le \exp \left( 2\theta s_j + 2C_8\theta \sum_{j_1 \text{ weak}} \lambda p_{jj_1} s_{j_1} \right) \le \exp \left( 2\theta s_j \left(1 + \frac{C_8}{c}\right) \right), \end{aligned} $$

where we used (48). Using now the convexity of the exponential function and $2\theta s_j(1 + C_8/c) \le 2(1 + C_8/c)$, we obtain

$$ \mathbb{E}[e^{\theta \bar{M}_j^{(n)}}] \le 1 + (e^{2(1+C_8/c)} - 1) \theta s_j. $$

To perform the recurrence step, we need $e^{2(1+C_8/c)} - 1 \le C_8$, which we can ensure by choosing $C_8 > e^2 - 1$ and $c$ sufficiently large. This concludes the proof of the first part of the proposition.

For the second part, we proceed exactly as above to bound $\mathbb{E}[e^{\theta \bar{M}_j^{(n)}}]$ by the expression $\exp(2\theta(1 + C_8/c)s_j)$. This is the required upper bound, by increasing the value of $C_8$ if necessary. Note also that we cannot further bound this without the hypothesis $\theta s_j \le 1$.
For the third and fourth parts, the computations are similar. For $\theta \le 1/\lambda s(a_{\text{str}})$, which ensures $\lambda\theta \le \min(1/2\lambda s(a_{\text{str}}), 1/s_j)$, we obtain

$$ \mathbb{E}[e^{\theta \bar{J}_i}] \le \prod_{j \text{ weak}} (1 + p_{ij} (\mathbb{E}[e^{\lambda \theta \bar{M}_j}] - 1)) \le e^{C_8 \theta \sigma_i}. $$

For $\theta \le \min(1, 1/(2\lambda s(a_{\text{str}})))$, which ensures $\theta/s_j \le \min(1/2\lambda s(a_{\text{str}}), 1/s_j)$, we obtain

$$ \mathbb{E}[e^{\theta \bar{K}_i}] \le e^{C_8 \theta \sum_{j \text{ weak}} p_{ij}} \le e^{2C_8 \theta \kappa_0 \pi_i}. \quad \square $$

**Corollary 5.** Under the same conditions, choosing a value $C_8 > 2$ for which Proposition 8(2) holds, we also have, for any $j$ weak,

$$ \mathbb{P}(\bar{M}_j \ge 2C_8 s(a_{\text{str}})) \le e^{-\lambda^{-1}}. \quad (112) $$

*Proof.* For $\theta = 1/(2\lambda s(a_{\text{str}}))$, Markov inequality and Proposition 8(2) yield

$$ \begin{aligned} \mathbb{P}(\bar{M}_j \ge 2C_8 s(a_{\text{str}})) &\le e^{-2C_8 \theta s(a_{\text{str}})} \mathbb{E}[e^{\theta \bar{M}_j}] \le e^{-2C_8 \theta s(a_{\text{str}})} e^{C_8 \theta s_j} \\ &\le e^{-C_8 \theta s(a_{\text{str}})} = e^{-C_8/2\lambda}, \end{aligned} $$

using also that the score $s_j$ associated to the weak vertex $j$ is smaller than $s(a_{\text{str}})$. $\square$

**Corollary 6.** Assume that the additional technical condition (H2) holds, yielding some $\alpha \in (0, 1]$, and $c_{(51)} > 0$, not depending on $\lambda$, such that

$$ \begin{aligned} s(a_{\text{str}}) &\le c_{(51)} \lambda^{-3+\alpha}, \\ s(a_{\text{str}}) &\le c_{(51)} \lambda^{-1+\alpha} \inf \left\{ \frac{s(x)}{T^{\text{loc}}(x)} : x < a_{\text{str}} \right\}. \end{aligned} $$

For any $c_{(114)} > 0$ and large $r > 0$, taking $c$ sufficiently large, there exists a constant $c_6$ such that for small $\lambda$, for any strong vertex $i$ and weak vertex $j$, we have

$$ \mathbb{P}(\bar{M}_j \ge \pi_{a_{\text{str}}} s_j) \le e^{-c_6 \lambda^{-\alpha}}, \quad (113) $$

$$ \mathbb{P}(\bar{J}_i \ge c_{(114)} \frac{s_i}{T^{\text{loc}}}) \le e^{-c_6 \lambda^{-\alpha}}, \quad (114) $$

$$ \mathbb{P}(\bar{K}_i \ge \frac{r}{10} \pi_i) \le e^{-c_6 \lambda^{-\alpha}}. \quad (115) $$

*Proof.* To obtain (113), proceed as in the proof of (112) to get

$$ \mathbb{P}(\bar{M}_j \ge \pi_{a_{\text{str}}} s_j) \le e^{-\frac{\pi_{a_{\text{str}}} - C_8}{2\lambda s(a_{\text{str}})}}, $$

and conclude by observing that $\lambda^2 \pi_{a_{\text{str}}}$ and $\lambda^{\alpha-3}/s(a_{\text{str}})$ are both lower bounded by positive constants. To obtain (114), take $\theta = 1/(\lambda s(a_{\text{str}}))$ to get

$$ \mathbb{P}(\bar{J}_i \ge c_{(114)} \frac{s_i}{T^{\text{loc}}}) \le e^{-c_{(114)} \theta \frac{s_i}{T^{\text{loc}}}} \mathbb{E}[e^{\theta \bar{J}_i}] \le e^{(-c_{(114)} + C_8/c) \frac{s_i}{\lambda s(a_{\text{str}}) T^{\text{loc}}}} \le e^{-\frac{c_{(114)} + c/\epsilon}{c_{(51)}} \lambda^{-\alpha}}, $$
using (H2), provided the constant $-c_{(114)} + C_8/c$ is negative, which we can ensure by choosing $c$ large. Finally, to obtain (115), take $\theta = \lambda^{2-\alpha}/2 \le \min(1, 1/2\lambda s(a_{\text{str}}))$ and $r/10$ larger than $C_8$ given by Proposition 8(4). Then,

$$ \mathbb{P}(\bar{K}_i \ge \frac{r}{10}\pi_x) \le e^{-(\frac{r}{10}-C_8)\theta\pi_i} \le e^{-c\lambda^{2-\alpha}\pi_{a_{\text{str}}}} $$

for some small constant $c$. We conclude again by observing that $\lambda^2\pi_{a_{\text{str}}}$ is lower bounded by a positive constant. $\square$

*Exploring and bounding the connectivities of the visited strong vertices.* We now turn to the true environment encountered by the infection. From now on, we assume that condition (H2) holds, so in particular we can apply Corollary 6. For a strong vertex $i \in G_t$, recall the definition of $J_i(t)$ and decompose it as $J_i^{\text{out}}(t) + J_i^{\text{in}}(t)$ with

$$ J_i^{\text{out}}(t) := \sum_{\substack{j \text{ weak} \\ (i,j) \text{ present}}} \lambda M_j(t), \quad J_i^{\text{in}}(t) := \sum_{\substack{j \text{ weak} \\ (j,i) \text{ present}}} \lambda M_j(t). $$

Recalling that there is (at most) one edge $(j, i)$ in $G_t$ pointing to $i$, the sum in the definition of $J_i^{\text{in}}$ contains only one or zero term. Similarly, we write $K_i(t) = K_i^{\text{out}}(t) + K_i^{\text{in}}(t)$ with

$$ K_i^{\text{out}}(t) := \sum_{\substack{j \text{ weak} \\ (i,j) \text{ present}}} \frac{M_j(t)}{s_j}, \quad K_i^{\text{in}}(t) := \sum_{\substack{j \text{ weak} \\ (j,i) \text{ present}}} \frac{M_j(t)}{s_j}. $$

For a weak vertex $i$, we also decompose $M_i(t) = M_i^{\text{out}}(t) + M_i^{\text{in}}(t)$ with

$$ M_i^{\text{out}}(t) := \tilde{s}_i + \sum_{\substack{j \text{ weak} \\ (i,j) \text{ present}}} \sum_{\substack{k \in t \\ d(i,k)=d(j,k)+1}} (2\lambda)^{d(i,k)} \tilde{s}_k, $$

$$ M_i^{\text{in}}(t) := \sum_{\substack{j \text{ weak} \\ (j,i) \text{ present}}} \sum_{\substack{k \in t \\ d(i,k)=d(j,k)+1}} (2\lambda)^{d(i,k)} \tilde{s}_k. $$

By the following lemma, the idealized environment provides an upper bound for the quantities $M_i^{\text{out}}$, $J_i^{\text{out}}$ and $K_i^{\text{out}}$.

**Lemma 4.**

* If $j$ is a weak vertex and $t \ge 0$, then, conditionally on $j$ being visited, the random variable $M_j^{\text{out}}(t)1_{t<T_{\text{bad}}^{\text{tree}}}$ is stochastically bounded by $\bar{M}_j$.

* If $i$ is a strong vertex and $t \ge 0$, then, conditionally on $i$ being visited, the random variables $J_i^{\text{out}}(t)1_{t<T_{\text{bad}}^{\text{tree}}}$ and $K_i^{\text{out}}(t)1_{t<T_{\text{bad}}^{\text{tree}}}$ are stochastically bounded by $\bar{J}_i$ and $\bar{K}_i$ respectively.

*Proof.* For a visited weak vertex, we can write $M_j^{\text{out}}(t)$ on the event $\{t < T_{\text{bad}}^{\text{tree}}\}$ as

$$ \tilde{s}_j + \sum_{n \ge 1} (2\lambda)^n \sum_{\substack{j_1, \dots, j_n \text{ distinct} \\ \text{weak vertices}}} 1_{\{\text{the edges } (j,j_1), \dots, (j_{n-1}, j_n) \text{ are in } G_t\}} \tilde{s}_{j_n}. $$
Recalling the bound $\tilde{s}_k \le 2s_k$, it remains to couple the graph and the random variables $C$ in such a way that for any directed path $(j, j_1, \dots, j_n)$ in $G_t$, we have $C_{j, \dots, j_n} = 1$. We proceed by induction on $n$. If $j_{n-1}$ is first visited at time $s \le t$, then for every weak vertex $j_n$ which is not in $G_{s-}$, the edge $(j_{n-1}, j_n)$ is present in $G_t$ with the stationary probability $p_{j_{n-1}, j_n}$. We then couple the connection at time $t$ with $C_{j, \dots, j_n}$. Note that we consider times smaller than $T_{\text{bad}}^{\text{tree}}$ so the connection of an edge $(j_{n-1}, j_n)$ is coupled to at most one variable $C_{j, \dots, j_n}$, thus maintaining the independence between the $C$ variables. The second part of the lemma with strong vertices is similar. $\square$

In the rest of this proof specifically, we write $\tilde{T}$ for $T_{\ell} \wedge T_{\text{bad}}^{\text{tree}} \wedge T_{\text{bad}}^{\text{deg}} \wedge \tilde{T}_{\text{deg}} \wedge T_{\text{hit}} \wedge t_0$.

**Corollary 7.** *Considering the same settings as in Corollary 6, say a weak vertex $j$ is bad at time $t$ if it is visited and satisfies*

$$M_j^{\text{out}}(t) \ge 2C_8s(a_{\text{str}}) \wedge \pi_{a_{\text{str}}} s_j.$$

Similarly, say a strong vertex $i$ is bad at time $t$ if it is visited and satisfies any of the following inequalities:

$$J_i^{\text{out}}(t) \ge c_{(114)} \frac{s_i}{T_i^{\text{loc}}}$$

$$K_i^{\text{out}}(t) \ge \frac{r}{10}\pi_i.$$

Finally, say a vertex is bad if it is bad at some time $t < \tilde{T}$. Then the probability of finding any bad vertex is bounded by $C_7 \ell^3 a^{-2\gamma} t_0 e^{-c_6 \lambda^{-\alpha}}$, for some finite constant $C_7$.

We stress that the definition of bad vertices in this corollary actually depends on the parameters $c_{(114)}$ and $r$ (that we have still not fixed), and also requires a constraint of large $c$ to apply Corollary 6. We discuss later how all these parameters are chosen.

*Proof.* Note that at times $t < \tilde{T}$, the number of visited vertices is bounded by $\ell$, while the number of nonvisited weak vertices in $G_t$ is bounded by $(2c_2a^{-\gamma} \vee 1/8\lambda^2)\ell$. Further, let $\ell' = \ell + (2c_2a^{-\gamma} \vee 1/8\lambda^2)\ell$, and choose a vertex $i$ conditioned to be in $G_{\tilde{T}}$. Suppose that the vertex turns bad at some time $t < \tilde{T}$. Then, with probability at least $1/e$, the vertex $i$ and the weak vertices in $G_t$ do not update until time $t + \tau$, with $\tau = 1/\kappa_0\ell'^2$. Therefore, with probability at least $e^{-1}$, we have $t + \tau < T_{\text{bad}}^{\text{tree}}$ and the value of $M_i$ (if $i$ is weak) or of $J_i$ and $K_i$ (if $i$ is strong) do not decrease on this time interval. In particular, there exists a time $s \in \tau \mathbb{N} \cap [0, \tilde{T} + \tau)$ which is less than $T_{\text{bad}}^{\text{tree}}$ and at which we observe a large value for $M_i(s)$ (or $J_i(s)$ or $K_i(s)$). By Lemma 4 and Corollaries 5 and 6, the probability that such a time $s$ exists, is bounded by $(t_0/\tau + 1)e^{-c_6 \lambda^{-\alpha}}$. We deduce successively a bound of $e(t_0/\tau + 1)e^{-c_6 \lambda^{-\alpha}}$ for the probability that a visited vertex turns bad, and a bound of $\ell e(t_0/\tau + 1)e^{-c_6 \lambda^{-\alpha}}$ for the probability of finding any bad vertex. $\square$

We now suppose that we do not encounter any bad vertex. We will then prove recursively that all the visited weak vertices $j$ satisfy

$$M_j(t) < 3C_8s(a_{\text{str}}) \wedge 2\pi_{a_{\text{str}}} s_j, \qquad (116)$$
at all times $t < \tilde{T}$. For the first visited weak vertex, we have $M_i(t) = M_i^{\text{out}}(t)$, so the bound follows from the fact that this vertex is good. Now, for a newly visited weak vertex $i$, we can bound $M_i^{\text{out}}$ by $2C_8s(a_{\text{str}}) \wedge \pi_{a_{\text{str}}}s_i$, so it suffices to bound $M_i^{\text{in}}$ by $C_8s(a_{\text{str}}) \wedge \pi_{a_{\text{str}}}s_i$. But the sum on $j$ in the definition of $M_i^{\text{in}}$ contains at most one term, which corresponds to a previously visited weak vertex $j$ and can be bounded by $2\lambda M_j$. By the recurrence hypothesis, we can further bound this term by $6\lambda C_8s(a_{\text{str}})$, which is smaller than $C_8s(a_{\text{str}})$ if $\lambda \le 1/6$. For small $\lambda$, we also obtain the bound $2\lambda M_j \le \pi_{a_{\text{str}}} \le \pi_{a_{\text{str}}}s_i$ by observing that we have $\pi_{a_{\text{str}}} \ge 1/20\kappa_0\lambda^{-2}$ and recalling that by condition (H2) we have $s(a_{\text{str}}) \le c_{(51)}\lambda^{-3+\alpha}$. Having proved that all visited weak vertices satisfy (116), we deduce the following bound for any visited strong vertex $i$.

$$J_i^{\text{in}} \le 3\lambda C_8s(a_{\text{str}}) \le 3\lambda^{\alpha} C_8 c_{(51)} \frac{s_i}{T_i^{\text{loc}}}$$

where we used condition (H2) to obtain the second inequality. Taking $\lambda$ small, we can further bound this by $c_{(114)}s_i/T_i^{\text{loc}}$. For the term $K_i^{\text{in}}$ we obtain similarly a simple bound, namely $2\pi_{a_{\text{str}}} \le 2\pi_i$. Combining this with the fact that all visited strong vertices are good, we obtain that they all satisfy, at all times $t < \tilde{T}$,

$$J_i(t) \le \frac{2c_{(114)}s_i}{T_i^{\text{loc}}} = 2c_{(114)}r\kappa_i t_i, \qquad (117)$$

$$K_i(t) \le \left(2 + \frac{r}{10}\right) \pi_i. \qquad (118)$$

We thus finally obtained bounds that resemble (102) and (103), and it only remains to explain in detail how we fix the values of $r$, $c$, $\varepsilon$, $c_{(114)}$.

First, recall we have to fix the values $c$, $r$ and $\varepsilon$, so that if the scoring function $s$ is assumed to satisfy Inequalities (48), (49) and (50) with this value of $c$, and if we use this value of $r$ in the definition the vertex scores $t_i$ (and thus of the configuration score $M(t)$), then we can ensure that Inequalities (102) and (103) are likely to be satisfied up until time $\tilde{T}$. In order to do so, we first request $c > 8r$ and fix a small value of $\varepsilon$ so as to have $4r/3c + \varepsilon \le 1/6$. Then, choosing $r$ large, we can ensure that we have $(4r - 6 - \frac{4r}{3c} - \varepsilon)/32 \ge 2 + r/10$, so that (102) is implied by (117). Now, choosing $c_{(114)} = 1/12r$, we also have $(\frac{1}{3} - \frac{4r}{3c} - \varepsilon) \ge \frac{1}{6} = 2c_{(114)}r$, so that (103) is implied by (118).

At this point, we are still free to increase the value of $r$ if we keep the request $c \ge 8r$ and $c_{(114)} = 1/12r$. We choose the (large) value of $r$ and $c_{(114)} = 1/12r$, so as to apply Corollary 6. Eventually, we fix the large value of $c$ necessary to apply Corollaries 5 and 6, fixing at the same time the value $C_8$. We then have a proper definition of bad vertices and can apply Corollary 7 to deduce that each visited strong vertex satisfies (117) and (118) and thus (102) and (103), with failure probability bounded by $C_7l^3a^{-2\gamma}t_0e^{-c_6\lambda^{-\alpha}}$. This bound on $P^{\text{conn}}$ is stretched exponentially small in $\lambda$, and hence negligible compared to $a$ as $\lambda \to 0$.
**Acknowledgements:** AL was partially supported by the CONICYT-PCHA/Doctorado nacional/2014-21141160 scholarship, grant GrHyDy ANR-20-CE40-0002, and by FONDECYT grant 11221346. PM was partially supported by DFG project 444092244 "Condensation in random geometric graphs" within the priority programme SPP 2265.

## REFERENCES

[1] Berger N, Borgs C, Chayes JT and Saberi A (2005) On the spread of viruses on the internet. In: *Proc. 16th Symposium on Discrete Algorithms*, (Association for Computing Machinery, New York), pp 301–310.

[2] Bollobás B, Janson S and Riordan O (2007). The phase transition in inhomogeneous random graphs. *Random Structures & Algorithms* **31**, 3 – 122.

[3] Can, VH (2017) Metastability for the contact process on the preferential attachment graph. *Internet Mathematics* https://doi.org/10.24166/im.08.2017, 45 pp.

[4] Cardona-Tobon N, Ortgiese M, Seiler M and Sturm A (2024). The contact process on dynamical random trees with degree dependence. *ArXiv Preprint 2406.12689*.

[5] Chatterjee S and Durrett R (2009) Contact processes on random graphs with power law degree distributions have critical value zero. *Ann. Probab.* **37**, 2332–2356.

[6] Durrett R and Liu X (1988) The contact process on a finite set. *Ann. Probab.* **16**, 1158–1173.

[7] Durrett R and Schonmann R (1988) The contact process on a finite set II. *Ann. Probab.* **16**, 1570–1583.

[8] Fernley J, Mörters P and Ortgiese M (2024). The contact process on a graph adapting to the infection. *ArXiv Preprint 2406.03037*.

[9] Ganesh A, Massoulie L and Towsley D (2005) The effect of network topology on the spread of epidemics. In: *Proceedings IEEE Infocom, Vol. 2, New York, NY*, 1455–1466.

[10] van der Hofstad R (2017) *Random graphs and complex networks, Volume I*. CUP, Cambridge.

[11] van der Hofstad R (2024) *Random graphs and complex networks, Volume II*. CUP, Cambridge.

[12] Jacob E, Linker A and Mörters P (2019) Metastability of the contact process on fast evolving scale-free networks. *Ann. Appl. Probab.* **29**, 2654–2699.

[13] Jacob E, Linker A, Mörters P (2022) The contact process on dynamical scale-free networks. *Ann. Inst. Henri Poincaré - Probab. et Stat.*, to appear.

[14] Jacob E and Mörters P (2017) The contact process on scale-free networks evolving by vertex updating. *Royal Society Open Science*, **4**: 170081.

[15] Liggett T (1999) *Stochastic interacting systems: contact, voter and exclusion processes*. Springer, New York.

[16] Mountford T, Valesin D, and Yao Q (2013). Metastable densities for the contact process on power law random graphs. *Electron. J. Probab.* **13**, 1–36.

[17] Mourrat JC, and Valesin D (2016). Phase transition of the contact process on random regular graphs. *Electron. J. Probab.* **21**, paper no. 31, 17 pp.

[18] Pastor-Satorras R and Vespignani A (2001). Epidemic spreading in scale-free networks. *Phys. Rev. Letters* **86**, 3200–3203.

[19] Seiler M, Sturm A (2023). Contact process in an evolving random environment. *Electron. J. Probab.* **28**, 1–61.

[20] Schapira B and Valesin D (2023) The contact process on dynamic regular graphs: monotonicity and subcritical phase. *ArXiv Preprint 2309.17040*.

[21] Zhang X, Moore C, Newman MEJ (2017). Random graph models for dynamic networks. *Eur. Phys. J. B* **90**, 200.

**Emmanuel Jacob**, Ecole Normale Supérieure de Lyon, Unité de Mathématiques Pures et Appliquées, UMR CNRS 5669, 46, Allée d'Italie, 69364 Lyon Cedex 07, France.

**Amitai Linker**, Departamento de Matemáticas, Facultad de Ciencias Exactas, Universidad Andrés Bello, Sazié 2212, Santiago, Chile.

**Peter Mörters**, Universität zu Köln, Mathematisches Institut, Weyertal 86–90, 50931 Köln, Germany.