\chapter{Preliminaries}\label{sec:pre}

This section gives the definitions and elementary facts used throughout the paper. We introduce the random graph process and its quantiles, record identities for the step at which colorability is lost, and prove the elementary estimates used below. The assumption $q \ge 3$ is used to color unicyclic components in \cref{lem:pre-cycles}(a), which supplies the lower bound in \cref{lem:pre-centre}(b). All remaining statements of this section hold for $q = 2$ as well.

Throughout the paper, we fix an integer $q \ge 3$. For each integer $k \ge 1$, we define $[k] = \{1, \dots, k\}$. We let $\log$ denote the natural logarithm. The constants in our statements may depend on $q$ and on the fixed parameters named in the statement, but not on $n$. Constants denoted by $C$ or $C'$ are local to the statement or proof in which they occur. We say that a statement holds \emph{for all large $n$} if there exists an integer $n_0$, depending only on $q$ and those fixed parameters, such that it holds for every $n \ge n_0$. Each assertion involving a fixed parameter holds separately at each value of that parameter; its onset may depend on that value.

\section{The edge process}\label{sec:pre-process}

We begin with multigraphs and their colorings. We will sample pairs of vertices with replacement and count degrees with multiplicity.

\begin{definition}\label{def:pre-multigraph}
Let $S$ be a finite set. We call a set $\{u, v\}$ with $u, v \in S$ and $u \ne v$ a \emph{pair} of $S$. We define a \emph{multigraph on $S$} to be a finite multiset $G$ of pairs of $S$. We call the elements of $G$, counted with multiplicity, the \emph{occurrences} of $G$. For a pair $e$ of $S$, we let $G + e$ denote the multigraph obtained from $G$ by adding one occurrence of $e$, and, if $e$ occurs in $G$, we let $G - e$ denote the multigraph obtained from $G$ by removing one occurrence of $e$. For pairs $p_1, \dots, p_k$ of $S$, we write $G + p_1 + \dots + p_k$ for the multigraph obtained from $G$ by adding one occurrence of each $p_i$, and $p_1 + \dots + p_k$ for the multigraph with occurrences $p_1, \dots, p_k$ (the empty multigraph if $k = 0$). We write $G \subset G'$ if every pair has at most the same multiplicity in $G$ as in $G'$. For $u \in S$, we define the \emph{degree} $\deg_G(u)$ to be the number of occurrences of $G$ that contain $u$. For $S' \subset S$, we let $G[S']$ denote the multigraph on $S'$ formed by the occurrences of $G$ that are pairs of $S'$. For a bijection $\phi \colon S \to S'$, we let $\phi G$ denote the multigraph on $S'$ whose occurrences are the pairs $\{\phi(u), \phi(v)\}$, where $\{u, v\}$ runs over the occurrences of $G$. We call a map $\sigma\colon S \to [q]$ a \emph{coloring} of $G$ if $\sigma(u) \ne \sigma(v)$ for every occurrence $\{u, v\}$ of $G$. We let $\Col(G)$ denote the set of colorings of $G$, and we say that $G$ is \emph{colorable} if $\Col(G) \neq \emptyset$.
\end{definition}

A multigraph has the same colorings as the simple graph formed by its distinct pairs. Repeated occurrences therefore do not affect colorability. They do affect degrees, and in this paper degrees always count occurrences. Note also that $\Col(G') \subset \Col(G)$ whenever $G \subset G'$.

\begin{definition}\label{def:pre-process}
Let $S$ be a finite set with at least two elements. We define an \emph{edge process on $S$} to be a sequence of independent random pairs of $S$, each uniformly distributed on the set of its $\binom{|S|}{2}$ pairs. For each integer $m \ge 0$, we call the multigraph whose occurrences are the first $m$ terms its \emph{time-$m$ graph}.
\end{definition}

Let $n \ge 2q$ be an integer. Throughout the paper, we let $(e_i)_{i \ge 1}$ denote an edge process on $[n]$. For each integer $m \ge 0$, we define $G_m = e_1 + \dots + e_m$. We let $\cF_m$ denote the $\sigma$-algebra generated by $e_1, \dots, e_m$. A vertex $u \in [n]$ belongs to $e_i$ with probability $(n - 1)/\binom{n}{2} = 2/n$, and $\deg_{G_m}(u)$ has the law $\Bin(m, 2/n)$. We define the hitting time of non-colorability
\begin{equation}\label{eq:pre-H}
H = \min\{m \ge 0 : G_m \text{ is not colorable}\}.
\end{equation}
We use the convention $\min\emptyset = \infty$. We set $A_q = 2q \log q + 2q + 1$. Since $G_0$ is empty, we have $H \ge 1$, and we will show in \cref{lem:pre-lifetime}(d) that $\E H \le A_q n$; in particular, $H$ is finite almost surely. On the event $\{H < \infty\}$, we let $\Gamma = G_{H - 1}$ denote the last colorable graph of the process, and we call $e_H$ the \emph{final edge}. Note that $\Pp(H > m) = \Pp(G_m \text{ is colorable})$ for all $m \ge 0$, and that this probability is nonincreasing in $m$.

We set
\begin{equation}\label{eq:pre-gamma}
\gamma_q = \frac{\log q}{\log(q/(q - 1))}.
\end{equation}
For every real $c_1 > \gamma_q$, the first-moment bound of \cref{lem:pre-centre}(a) implies that the probability that $G_{\lfloor c_1 n\rfloor}$ is colorable tends to zero. Thus $\gamma_q$ is an upper bound for the threshold, measured in edges per vertex. We fix a real number $\Lambda > \gamma_q + 1$. Throughout the paper, we allow constants and the onset of statements for all large $n$ to depend on this fixed $\Lambda$. In the final proofs, we set $\Lambda = \gamma_q + 2$. We set $M = \lfloor \Lambda n \rfloor$ and
\begin{equation}\label{eq:pre-V}
V = \min(H - 1, M).
\end{equation}
The cap $M$ makes $V$ a bounded function of $e_1, \dots, e_M$, which is convenient for variance bounds. By \cref{lem:pre-centre}(a), the quantiles defined below are smaller than $M$ for all large $n$.

\begin{definition}\label{def:pre-quantile}
For $\eta \in (0, 1/2]$, we define the \emph{lower quantile} $L_n(\eta)$ and the \emph{upper quantile} $U_n(\eta)$ by
\begin{equation}\label{eq:pre-quantile}
\begin{aligned}
L_n(\eta) &= \min\{m \ge 0 : \Pp(V \le m) \ge \eta\}, \\
U_n(\eta) &= \max\{m \in \{0, \dots, M\} : \Pp(V \ge m) \ge \eta\},
\end{aligned}
\end{equation}
where $m$ ranges over integers, and we call $w_n(\eta) = U_n(\eta) - L_n(\eta)$ the \emph{window} at level $\eta$. We also set $\eta_0 = e^{-2\Lambda}/8$.
\end{definition}

The two sets in \eqref{eq:pre-quantile} are nonempty, since $\Pp(V \le M) = 1$ and $\Pp(V \ge 0) = 1$. The first identity also implies that $L_n(\eta) \le M$. In later sections, we restrict the quantile level to $\eta \in (0, \eta_0]$. We use the value of $\eta_0$ in \cref{app:conv}. When $n$ and $\eta$ are fixed, we write $L$, $U$, and $w$ for $L_n(\eta)$, $U_n(\eta)$, and $w_n(\eta)$.

\begin{lemma}\label{lem:pre-quantile}
Let $\eta \in (0, 1/2]$. Then $L \le U \le M$. Further, we have
\begin{equation}\label{eq:pre-quantile-tails}
\begin{aligned}
\Pp(H > m) &> 1 - \eta \qquad \text{for all integers } 0 \le m \le L, \\
\Pp(H > m) &< \eta \qquad \text{for all integers } U < m \le M.
\end{aligned}
\end{equation}
\end{lemma}

\begin{proof}
By the minimality of $L$, we have $\Pp(V \le L - 1) < \eta$ (if $L = 0$, this holds because $V \ge 0$). Hence
\[
\Pp(V \ge L) = 1 - \Pp(V \le L - 1) > 1 - \eta \ge \eta,
\]
where we used $\eta \le 1/2$ in the last step. Since also $L \le M$, the integer $L$ belongs to the set that defines $U$, and therefore $L \le U$. The bound $U \le M$ holds by the definition of $U$.

Next, we observe that for every integer $m \le M$,
\begin{equation}\label{eq:pre-V-H}
\{V \ge m\} = \{H - 1 \ge m\} = \{H > m\}.
\end{equation}
Taking $m = L$ in \eqref{eq:pre-V-H}, we find that
\[
\Pp(H > L) = \Pp(V \ge L) > 1 - \eta,
\]
and the first bound in \eqref{eq:pre-quantile-tails} follows because $\Pp(H > m)$ is nonincreasing in $m$. Now let $U < m \le M$. By the maximality of $U$, the integer $m$ does not belong to the set that defines $U$, and \eqref{eq:pre-V-H} implies that $\Pp(H > m) = \Pp(V \ge m) < \eta$.
\end{proof}

\section{Frozen pairs}\label{sec:pre-frozen}

The final edge of the process joins two vertices that receive the same color in every coloring of the last colorable graph. We now introduce the corresponding notions.

\begin{definition}\label{def:pre-frozen}
Let $S$ be a finite set with $N \ge 2$ elements, and let $G$ be a multigraph on $S$. For $u, v \in S$, we write $u \sim _G v$ if $G$ is colorable and $\sigma(u) = \sigma(v)$ for all $\sigma \in \Col(G)$. We call a pair $\{u, v\}$ of $S$ a \emph{frozen pair} of $G$ if $u \sim _Gv$. If $G$ is colorable, we call the set $C_G(u) = \{v \in S : u \sim _G v\}$ the \emph{frozen class} of $u \in S$. If $G$ is colorable, let $C_1, \dots, C_k$ denote its distinct frozen classes. We define
\begin{equation}\label{eq:pre-kappa}
\kappa(G) = \binom{N}{2}^{-1} \#\{\text{frozen pairs of } G\}, \qquad Q(G) = \sum_{i = 1}^k \Big(\frac{|C_i|}{N}\Big)^2,
\end{equation}
and we set $Q(G) = 0$ if $G$ is not colorable.
\end{definition}

The relation $\sim _G$ is an equivalence relation on $S$ whenever $G$ is colorable, since it is defined by equalities of colors. Its classes are the frozen classes, and $u \in C_G(u)$ for all $u \in S$. We say that $u$ \emph{lies in a frozen pair} of $G$ if $|C_G(u)| \ge 2$. We have $\kappa(G) = 0$ when $G$ is not colorable, since $\sim _G$ is then empty. Observe that $\kappa(G)$ is the probability that a uniformly random pair of $S$ is a frozen pair of $G$. A frozen pair of $G$ is not an occurrence of $G$, since every coloring of $G$ gives different colors to the endpoints of each occurrence.

Throughout the paper, we define numerical statistics constructed from colorings or frozen classes to be $0$ when the multigraph is not colorable, and set-valued statistics to be the empty set. We evaluate expressions involving frozen classes, including logarithms and quotients, on the colorable event, and define the entire expression to be $0$ otherwise. In particular, $\Col(G) = \emptyset$ when $G$ is not colorable. We use this convention in every identity involving these statistics.

Culberson and Gent studied frozen pairs in random graph coloring and the graph obtained by merging their equivalence classes \cite[Sections~2.1 and~3.2]{culberson2001frozen}. Their tests for frozen and free pairs use edge addition and vertex identification, respectively \cite[Section~2.2]{culberson2001frozen}. Our relation $\sim _G$ quantifies over all colorings of $G$.

\begin{lemma}\label{lem:pre-frozen}
Let $S$ be a finite set with $N \ge 2$ elements, and let $G$ be a multigraph on $S$.
\begin{enumerate}[label=(\alph*)]
\item For all distinct $u, v \in S$, the multigraph $G + \{u, v\}$ is colorable if and only if $G$ is colorable and $u \not \sim _G v$. If $f$ is a uniformly random pair of $S$, then
\[
\Pp(G \text{ is colorable and } G + f \text{ is not colorable}) = \kappa(G).
\]
\item Let $G'$ be a colorable multigraph on $S$ with $G \subset G'$. Then $G$ is colorable, $u \sim _G v$ implies $u \sim _{G'} v$ for all $u, v \in S$, $C_G(u) \subset C_{G'}(u)$ for all $u \in S$, and $\kappa(G) \le \kappa(G')$.
\item If $G$ is colorable, then
\[
Q(G) = \Big(1 - \frac 1N\Big) \kappa(G) + \frac 1N,
\]
and $|C_G(u)| \le N Q(G)^{1/2}$ for all $u \in S$.
\end{enumerate}
\end{lemma}

\begin{proof}
We begin with (a). Observe that
\[
\Col(G + \{u, v\}) = \{\sigma \in \Col(G) : \sigma(u) \neq \sigma(v)\}.
\]
This set is empty if and only if either $\Col(G) = \emptyset$, or $\Col(G) \neq \emptyset$ and $\sigma(u) = \sigma(v)$ for all $\sigma \in \Col(G)$. By the definition of $\sim _G$, the second alternative means that $u \sim _G v$. The second statement of (a) follows by averaging over the $\binom{N}{2}$ values of $f$.

To prove (b), we use the inclusion $\Col(G') \subset \Col(G)$, which implies that $G$ is colorable. Suppose that $u \sim _G v$. Then every $\sigma \in \Col(G')$ is a coloring of $G$ and therefore satisfies $\sigma(u) = \sigma(v)$. This means that $u \sim _{G'} v$. The remaining statements of (b) follow.

Finally, let $C_1, \dots, C_k$ be the distinct frozen classes of $G$. A frozen pair is a pair of distinct elements of one class, so
\[
\sum_{i = 1}^k |C_i|^2 = \sum_{i = 1}^k |C_i| (|C_i| - 1) + \sum_{i = 1}^k |C_i| = 2 \#\{\text{frozen pairs of } G\} + N = N (N - 1) \kappa(G) + N.
\]
Dividing by $N^2$, we obtain the formula for $Q(G)$ in (c). The bound on $|C_G(u)|$ follows from $(|C_G(u)|/N)^2 \le Q(G)$.
\end{proof}

\Cref{lem:pre-frozen}(a) is the elementary case of the addition--identification relation for chromatic polynomials \cite[Section~3, Theorem~1]{read1968introduction}. For nonadjacent $u$ and $v$, this relation splits the colorings of $G$ into the colorings of $G + \{u, v\}$ and the colorings that are constant on $\{u, v\}$. The latter correspond to the colorings of the graph obtained from $G$ by identifying $u$ and $v$.

\section{The final edge}\label{sec:pre-hazard}

We now express the law of the final edge $e_H$ through the frozen pairs of the graphs $G_m$ at deterministic times. Culberson and Gent used frozen-pair counts to compute conditional one-edge survival probabilities in a process without replacement \cite[Section~3.3]{culberson2001frozen}; here independent sampling with replacement gives the normalization $\binom{n}{2}^{-1}$. For random $2$-SAT, a related conditional probability is computed in \cite[Section~3.3]{bollobas2001scaling}; our proofs follow the same idea. They are short applications of \cref{lem:pre-frozen}(a).

\begin{lemma}\label{lem:pre-hazard}
For all integers $m \ge 0$, we have
\begin{equation}\label{eq:pre-hazard}
\Pp(H = m + 1 \mid \cF_m) = \kappa(G_m) \qquad \text{almost surely}.
\end{equation}
For every $\cF_m$-measurable random variable $\zeta \ge 0$, we have $\E[\zeta \kappa(G_m)] = \E[\zeta \ind\{H = m + 1\}]$. In particular, if $\mathcal J$ is a set of nonnegative integers and $\zeta_m$ is an $\cF_m$-measurable random variable with values in $[0, 1]$ for each $m \in \mathcal J$, then
\begin{equation}\label{eq:pre-hazard-sum}
\sum_{m \in \mathcal J} \E[\zeta_m \kappa(G_m)] \le \Pp(H - 1 \in \mathcal J) \le 1.
\end{equation}
\end{lemma}

\begin{proof}
We have
\[
\{H = m + 1\} = \{G_m \text{ is colorable and } G_m + e_{m + 1} \text{ is not colorable}\},
\]
where $G_m$ is a function of $e_1, \dots, e_m$, and $e_{m + 1}$ is a uniformly random pair of $[n]$ independent of $\cF_m$. Using \cref{lem:pre-frozen}(a) with $G = G_m$ and $f = e_{m + 1}$, we obtain \eqref{eq:pre-hazard}. Multiplying \eqref{eq:pre-hazard} by $\zeta$ and taking expectations gives the second statement. To prove \eqref{eq:pre-hazard-sum}, we use the second statement for each $m \in \mathcal J$ and the bound $\zeta_m \le 1$, and we find
\[
\sum_{m \in \mathcal J} \E[\zeta_m \kappa(G_m)] = \sum_{m \in \mathcal J} \E[\zeta_m \ind\{H = m + 1\}] \le \sum_{m \in \mathcal J} \Pp(H = m + 1) = \Pp(H - 1 \in \mathcal J),
\]
where the last equality holds because the events $\{H = m + 1\}$ are disjoint.
\end{proof}

To isolate final edges with prescribed properties, we use sets of frozen pairs. Let $\cE$ be a set whose elements are of the form $(G, e)$, where $G$ is a colorable multigraph on $[n]$ and $e$ is a frozen pair of $G$. For a multigraph $G$ on $[n]$, we define
\begin{equation}\label{eq:pre-kappaE}
\kappa_{\cE}(G) = \binom{n}{2}^{-1} \#\{e : (G, e) \in \cE\}.
\end{equation}
Then $0 \le \kappa_{\cE}(G) \le \kappa(G)$, and $\kappa_{\cE}(G) = 0$ if $G$ is not colorable. For a permutation $\phi$ of $[n]$ and a pair $e = \{u, v\}$, we write $\phi(e) = \{\phi(u), \phi(v)\}$. We say that $\cE$ is \emph{invariant under relabeling} if, for every permutation $\phi$ of $[n]$, we have $(\phi G, \phi(e)) \in \cE$ if and only if $(G, e) \in \cE$. We call a function $h$ on multigraphs on $[n]$ \emph{invariant under relabeling} if $h(\phi G) = h(G)$ for every multigraph $G$ and permutation $\phi$ of $[n]$. We call the law of a random multigraph $G$ on $[n]$ \emph{invariant under relabeling} if $\phi G$ has the law of $G$ for every permutation $\phi$ of $[n]$. For example, the law of $G_m$ is invariant under relabeling for every $m \ge 0$.

\begin{lemma}\label{lem:pre-terminal}
Let $\cE$ be a set whose elements are of the form $(G, e)$, where $G$ is a colorable multigraph on $[n]$ and $e$ is a frozen pair of $G$.
\begin{enumerate}[label=(\alph*)]
\item Let $h_0, h_1, \dots$ be functions with values in $[0, \infty)$ on the set of multigraphs on $[n]$, let $L' \ge 0$ be an integer, and let $U'$ be an integer with $U' > L'$ or let $U' = \infty$. When $U' = \infty$, we define $\{L' < H \le U'\}$ to mean $\{L' < H < \infty\}$. Then
\begin{equation}\label{eq:pre-terminal}
\E\big[h_{H - 1}(\Gamma) \ind\{L' < H \le U', \, (\Gamma, e_H) \in \cE\}\big] = \sum_{m = L'}^{U' - 1} \E\big[\kappa_{\cE}(G_m) h_m(G_m)\big].
\end{equation}
If $U' = \infty$, the sum runs over all $m \ge L'$. In particular, \eqref{eq:pre-terminal} holds with $h_m = h$ for all $m$, for every function $h \ge 0$ on multigraphs on $[n]$.
\item Suppose that $\cE$ and a function $h \ge 0$ on multigraphs on $[n]$ are invariant under relabeling, and let $G$ be a random multigraph on $[n]$ whose law is invariant under relabeling. Then for all distinct $a, b \in [n]$, we have
\begin{equation}\label{eq:pre-fixed-pair}
\E\big[\kappa_{\cE}(G) h(G)\big] = \E\big[\ind\{(G, \{a, b\}) \in \cE\} h(G)\big].
\end{equation}
\end{enumerate}
\end{lemma}

\begin{proof}
We begin with (a). Fix $m \ge 0$, and suppose that $(G_m, e_{m + 1}) \in \cE$. Then $G_m$ is colorable and $e_{m + 1}$ is a frozen pair of $G_m$, so that $G_m + e_{m + 1}$ is not colorable by \cref{lem:pre-frozen}(a), and $H = m + 1$. Since $\Gamma = G_m$ and $e_H = e_{m + 1}$ on the event $\{H = m + 1\}$, it follows that
\begin{equation}\label{eq:pre-terminal-event}
\{H = m + 1, \, (\Gamma, e_H) \in \cE\} = \{(G_m, e_{m + 1}) \in \cE\}.
\end{equation}

The pair $e_{m + 1}$ is uniformly distributed on the pairs of $[n]$ and independent of $\cF_m$. Therefore the conditional probability of the event \eqref{eq:pre-terminal-event} given $\cF_m$ is $\kappa_{\cE}(G_m)$. Since $h_m(G_m)$ is nonnegative and $\cF_m$-measurable, we obtain
\[
\begin{aligned}
\E\big[h_{H - 1}(\Gamma) \ind\{H = m + 1, \, (\Gamma, e_H) \in \cE\}\big] &= \E\big[h_m(G_m) \ind\{(G_m, e_{m + 1}) \in \cE\}\big]\\
&= \E\big[\kappa_{\cE}(G_m) h_m(G_m)\big].
\end{aligned}
\]
The event $\{L' < H \le U'\}$ is the disjoint union of the events $\{H = m + 1\}$ over $L' \le m \le U' - 1$. Summing the previous display over these $m$, we obtain \eqref{eq:pre-terminal}. (All terms are nonnegative, and the exchange of sum and expectation is justified even when the sum is infinite.)

We now prove (b). By the definition \eqref{eq:pre-kappaE}, we have
\[
\kappa_{\cE}(G) h(G) = \binom{n}{2}^{-1} \sum_{e} \ind\{(G, e) \in \cE\} h(G),
\]
where the sum runs over the pairs $e$ of $[n]$. For each pair $e$, we choose a permutation $\phi$ of $[n]$ with $\phi(e) = \{a, b\}$. The invariance of $\cE$ and $h$ gives
\[
\ind\{(G, e) \in \cE\} h(G) = \ind\{(\phi G, \{a, b\}) \in \cE\} h(\phi G),
\]
and since $\phi G$ has the law of $G$, the expectation of the right side is the right side of \eqref{eq:pre-fixed-pair}. Averaging over the $\binom{n}{2}$ pairs $e$ completes the proof.
\end{proof}

\Cref{lem:pre-terminal}(a) converts statements about the final edge into statements about frozen pairs at deterministic times. We use this identity to estimate probabilities involving the final edge.

\section{Lifetime}\label{sec:pre-lifetime}

We will control the window by the expected number of further uniformly random pairs that the last colorable graph $\Gamma$ can accept. We now define this quantity for a general multigraph.

\begin{definition}\label{def:pre-lifetime}
Let $S$ be a finite set with $N \ge 2$ elements, let $G$ be a multigraph on $S$, and let $f_1, f_2, \dots$ be an edge process on $S$. We define
\begin{equation}\label{eq:pre-T}
T_G = \min\{k \ge 0 : G + f_1 + \dots + f_k \text{ is not colorable}\} \in \{0, 1, \dots\} \cup \{\infty\}.
\end{equation}
We call $r(G) = \E T_G \in [0, \infty]$ the \emph{expected lifetime} of $G$, and for integers $b \ge 0$, we set $r_b(G) = \E \min(T_G, b)$.
\end{definition}

In words, $r(G)$ is the expected number of independent uniformly random pairs that must be added to $G$ to make it non-colorable. The law of $T_G$ is the same for every edge process on $S$, and therefore $r(G)$ and $r_b(G)$ are functions of $G$. Since $\min(T_G, b) = \sum_{k = 0}^{b - 1} \ind\{T_G > k\}$, we have
\begin{equation}\label{eq:pre-rb}
r_b(G) = \sum_{k = 0}^{b - 1} \Pp(T_G > k).
\end{equation}

\begin{lemma}\label{lem:pre-lifetime}
Let $S$ be a finite set with $N \ge 2$ elements, and let $G$ and $G'$ be multigraphs on $S$.
\begin{enumerate}[label=(\alph*)]
\item If $G$ is not colorable, then $r(G) = 0$ and $r_b(G) = 0$ for all $b \ge 0$. If $G$ is colorable, then $1 \le r_b(G) \le \min(b, r(G))$ for all integers $b \ge 1$, and $r_b(G)$ is nondecreasing in $b$. If $G$ is colorable and $N \ge 2q$, then
\begin{equation}\label{eq:pre-Aq}
r(G) \le A_q N.
\end{equation}
\item If $G \subset G'$, then $r(G') \le r(G)$ and $r_b(G') \le r_b(G)$ for all $b \ge 0$. If $\phi \colon S \to S'$ is a bijection, then $r(\phi G) = r(G)$ and $r_b(\phi G) = r_b(G)$ for all $b \ge 0$.
\item If $\kappa(G) > 0$, then $r(G) \le 1/\kappa(G)$.
\item For the edge process on $[n]$ and all integers $m \ge 0$, we have
\begin{equation}\label{eq:pre-r-conditional}
r(G_m) = \E\big[(H - m) \ind\{H > m\} \mid \cF_m\big] \qquad \text{almost surely}.
\end{equation}
In particular, $\E H = r(G_0) \le A_q n$.
\end{enumerate}
\end{lemma}

\begin{proof}
We begin with (a). We have $T_G = 0$ if $G$ is not colorable, and $T_G \ge 1$ if $G$ is colorable, so that $\min(T_G, b) \ge 1$ for $b \ge 1$ in the latter case. The bounds $\min(T_G, b) \le b$ and $\min(T_G, b) \le T_G$, and the monotonicity in $b$, hold pointwise.

We now prove \eqref{eq:pre-Aq}. Let $\emptyset_S$ denote the empty multigraph on $S$, and compute $T_G$ and $T_{\emptyset_S}$ from the same edge process. If $G + f_1 + \dots + f_k$ is colorable, then so is $f_1 + \dots + f_k$. This implies that $T_G \le T_{\emptyset_S}$, and it suffices to bound $r(\emptyset_S)$.

Let $\sigma\colon S \to [q]$ be a map. For $i \in [q]$, we define $b_i = |\sigma^{-1}(\{i\})|$. Using the convexity of $x \mapsto x(x - 1)/2$ and Jensen's inequality, we have
\[
\#\{\text{pairs } \{u, v\} \text{ of } S : \sigma(u) = \sigma(v)\} = \sum_{i = 1}^q \frac{b_i (b_i - 1)}{2} \ge \frac{N (N/q - 1)}{2}.
\]
The fraction of pairs of $S$ on which $\sigma$ is constant is at least $(N/q - 1)/(N - 1)$, which is at least $1/(2q)$ when $N \ge 2q$.

It follows that $\sigma$ is a coloring of $f_1 + \dots + f_k$ with probability at most $(1 - 1/(2q))^k \le e^{-k/(2q)}$. Taking a union bound over the $q^N$ maps $\sigma$, we obtain
\[
\Pp(T_{\emptyset_S} > k) = \Pp(f_1 + \dots + f_k \text{ is colorable}) \le \min\big(1, q^N e^{-k/(2q)}\big).
\]
Let $k_0 = \lceil 2 q N \log q \rceil$. For $k \ge k_0$, we have $q^N e^{-k/(2q)} \le e^{-(k - k_0)/(2q)}$, and therefore
\[
\begin{aligned}
r(\emptyset_S) = \sum_{k \ge 0} \Pp(T_{\emptyset_S} > k) &\le k_0 + \sum_{j \ge 0} e^{-j/(2q)} = k_0 + \frac{1}{1 - e^{-1/(2q)}}\\
&\le 2 q N \log q + 2q + 2 \le A_q N.
\end{aligned}
\]
In the second line, we used $1/(1 - e^{-x}) \le 1 + 1/x$ for $x > 0$ and $2q + 2 \le (2q + 1) N$, which holds since $N \ge 2$.

For (b), we compute $T_G$ and $T_{G'}$ from the same edge process. If $G' + f_1 + \dots + f_k$ is colorable, then so is $G + f_1 + \dots + f_k$. We conclude that $T_{G'} \le T_G$ pointwise, which gives the inequalities.

Now let $\phi \colon S \to S'$ be a bijection. Then $(\phi(f_k))_{k \ge 1}$ is an edge process on $S'$, and $\sigma \mapsto \sigma \circ \phi^{-1}$ is a bijection from $\Col(G + f_1 + \dots + f_k)$ to $\Col(\phi G + \phi(f_1) + \dots + \phi(f_k))$. The random variable $T_{\phi G}$, computed from $(\phi(f_k))$, coincides with $T_G$, which gives the invariance.

Next, we prove (c). Let $\mathcal Y$ denote the set of frozen pairs of $G$. Then $|\mathcal Y| = \kappa(G)\binom{N}{2} > 0$. We set
\[
T' = \min\{k \ge 1 : f_k \in \mathcal Y\}.
\]
Then $T'$ has the geometric law with parameter $\kappa(G)$ on $\{1, 2, \dots\}$, and $\E T' = 1/\kappa(G)$. It remains to show that $T_G \le T'$.

This holds if $G + f_1 + \dots + f_{T' - 1}$ is not colorable. Otherwise, every coloring of $G + f_1 + \dots + f_{T' - 1}$ is a coloring of $G$ and is constant on the frozen pair $f_{T'}$, so $G + f_1 + \dots + f_{T'}$ is not colorable.

Finally, we prove (d). For a multigraph $G$ on $[n]$ and a sequence $(p_k)_{k \ge 1}$ of pairs of $[n]$, let
\[
\Theta\big(G, (p_k)_{k \ge 1}\big) = \min\{k \ge 0 : G + p_1 + \dots + p_k \text{ is not colorable}\}.
\]
By the definition of $T_G$, we have $\E \Theta(G, (f_k)_{k \ge 1}) = r(G)$ for every multigraph $G$ on $[n]$ and every edge process $(f_k)$ on $[n]$.

If $H > m$, then $H - m = \Theta(G_m, (e_{m + k})_{k \ge 1})$. If $H \le m$, then $G_m$ is not colorable and $\Theta(G_m, (e_{m + k})_{k \ge 1}) = 0$. Hence
\[
(H - m) \ind\{H > m\} = \Theta\big(G_m, (e_{m + k})_{k \ge 1}\big).
\]
The sequence $(e_{m + k})_{k \ge 1}$ is an edge process on $[n]$ independent of $\cF_m$, and $G_m$ is a function of $e_1, \dots, e_m$. Since $\Theta \ge 0$, the conditional expectation of the right side given $\cF_m$ is $r(G_m)$, which is \eqref{eq:pre-r-conditional}. Taking $m = 0$ and expectations, and using (a) with $N = n \ge 2q$, we obtain $\E H = r(G_0) \le A_q n$.
\end{proof}

The identity \eqref{eq:pre-r-conditional} holds at deterministic times $m$. Since $H - 1$ is not a stopping time, we always pass from $\Gamma$ to the graphs $G_m$ through \cref{lem:pre-terminal} when we bound $r(\Gamma)$.

\begin{lemma}\label{lem:pre-classmass}
Let $S$ be a finite set with $N \ge 2q$ elements, let $G$ be a colorable multigraph on $S$, and let $y > 0$. If $r(G) > y$, then
\begin{equation}\label{eq:pre-classmass}
Q(G) \le \frac{1 + A_q}{y}, \qquad |C_G(u)| \le N \Big(\frac{1 + A_q}{y}\Big)^{1/2} \quad \text{for all } u \in S.
\end{equation}
\end{lemma}

\begin{proof}
By \cref{lem:pre-lifetime}(c), we have $\kappa(G) r(G) \le 1$ (this is trivial if $\kappa(G) = 0$). \Cref{lem:pre-lifetime}(a) gives $r(G)/N \le A_q$. Using \cref{lem:pre-frozen}(c), we obtain
\[
Q(G) r(G) = \Big(1 - \frac 1N\Big) \kappa(G) r(G) + \frac{r(G)}{N} \le 1 + A_q.
\]
Since $r(G) > y$, this gives the first bound in \eqref{eq:pre-classmass}, and the second follows from the bound $|C_G(u)| \le N Q(G)^{1/2}$ of \cref{lem:pre-frozen}(c).
\end{proof}

\section{Poissonization and splitting}\label{sec:pre-poisson}

When the number of sampled pairs is Poisson, splitting the possible pairs into disjoint sets gives independent sublists. We record the facts that we use.

\begin{definition}\label{def:pre-poissonized}
Let $S$ be a finite set with at least two elements, let $f_1, f_2, \dots$ be an edge process on $S$, and let $(\Pi_t)_{t \ge 0}$ be a rate-one Poisson counting process independent of $(f_i)$. We define a \emph{list} to be a finite sequence. We call the multigraph-valued process $t \mapsto f_1 + \dots + f_{\Pi_t}$ the \emph{Poissonized process on $S$}. We call its value at time $t$ the Poissonized process on $S$ at time $t$. For $a \in S$, $S' \subset S \setminus \{a\}$, and $t \ge 0$, we define the \emph{neighbor list of $a$ in $S'$ at time $t$} by including one entry $x$ for every index $i \le \Pi_t$ with $f_i = \{a, x\}$ and $x \in S'$, in increasing order of $i$.
\end{definition}

A neighbor list may have repeated entries. For $\mu \ge 0$ and a finite set $E'$ with a probability measure $\nu'$, we call a random list a \emph{list of $\Pois(\mu)$ independent elements of $E'$ with law $\nu'$} if its length has the $\Pois(\mu)$ law and, conditionally on its length, its entries are independent with law $\nu'$. Throughout the paper, we let $(\Pi_t)_{t \ge 0}$ denote a rate-one Poisson counting process independent of $(e_i)$, and we set $G(t) = G_{\Pi_t}$ for $t \ge 0$. Thus $(G(t))_{t \ge 0}$ is the Poissonized process on $[n]$, and the law of $G(t)$ is invariant under relabeling for every $t \ge 0$. For the rest of this section, let $S$ be a finite set with at least two elements. We let $(G^S_m)_{m \ge 0}$ denote the time-$m$ graphs of an edge process on $S$, and $(G^S(t))_{t \ge 0}$ the Poissonized process on $S$ built from it.

\begin{lemma}\label{lem:pre-poisson}
Let $S$ be a finite set with at least two elements, and let $h \ge 0$ be a function on multigraphs on $S$. For every real $\theta > 0$, we have
\begin{equation}\label{eq:pre-poisson}
\int_0^\infty \E h\big(G^S(\theta t)\big) \dd t = \frac{1}{\theta} \sum_{m \ge 0} \E h(G^S_m),
\end{equation}
where both sides may be infinite.
\end{lemma}

\begin{proof}
For $s \ge 0$, the random variable $\Pi_s$ is independent of the edge process and has the $\Pois(s)$ law, so that
\[
\E h\big(G^S(s)\big) = \sum_{m \ge 0} e^{-s} \frac{s^m}{m!} \E h(G^S_m).
\]
We insert this identity with $s = \theta t$ into the left side of \eqref{eq:pre-poisson}, and we exchange sum and integral, which is allowed by Tonelli's theorem since all terms are nonnegative. Using that
\[
\int_0^\infty e^{-\theta t} \frac{(\theta t)^m}{m!} \dd t = \frac{1}{\theta}
\]
for every integer $m \ge 0$, we obtain \eqref{eq:pre-poisson}.
\end{proof}

\begin{lemma}\label{lem:pre-split}
\begin{enumerate}[label=(\alph*)]
\item Let $E$ be a finite set, let $\nu$ be a probability measure on $E$, let $X_1, X_2, \dots$ be independent random elements of $E$ with law $\nu$, and let $I$ be an independent random variable with the $\Pois(\mu)$ law, where $\mu \ge 0$. Let $E_1, \dots, E_{J}$ be a partition of $E$ into sets with $\nu(E_j) > 0$. Then the subsequences of $(X_1, \dots, X_I)$ formed by the terms in $E_1, \dots, E_{J}$ are independent, and for each $j$, the subsequence formed by the terms in $E_j$ is a list of $\Pois(\mu \nu(E_j))$ independent elements of $E_j$ with law $\nu(\, \cdot \mid E_j)$.
\item Let $S$ be a finite set with $N \ge 3$ elements, let $S_0 \subset S$, and set $S' = S \setminus S_0$. Suppose that $S'$ has at least two elements, and let $t \ge 0$. Then the multigraphs $G^S(t)[S']$ and $G^S(t)[S_0]$ and the neighbor lists of the vertices $a \in S_0$ in $S'$ at time $t$ are independent. Further, $G^S(t)[S']$ has the law of the Poissonized process on $S'$ at time $t \binom{|S'|}{2}/\binom{N}{2}$, and each of these neighbor lists is a list of $\Pois(t |S'|/\binom{N}{2})$ independent uniformly random elements of $S'$.
\item Let $S$ be a finite set with $N \ge 3$ elements, let $a \in S$, and let $t \ge 0$. Then $\deg_{G^S(t)}(a)$ is the length of the neighbor list of $a$ in $S \setminus \{a\}$ at time $t$, and $G^S(t)$ is obtained from $G^S(t)[S \setminus \{a\}]$ by adding one occurrence $\{a, x\}$ for each entry $x$ of this list. The list is independent of $G^S(t)[S \setminus \{a\}]$, it is a list of $\Pois(2t/N)$ independent uniformly random elements of $S \setminus \{a\}$, and $G^S(t)[S \setminus \{a\}]$ has the law of the Poissonized process on $S \setminus \{a\}$ at time $(N - 2) t/N$.
\end{enumerate}
\end{lemma}

\begin{proof}
We begin with (a). Fix integers $k_1, \dots, k_{J} \ge 0$, let $k = k_1 + \dots + k_{J}$, and fix sequences
\[
y^{(j)} = (y^{(j)}_1, \dots, y^{(j)}_{k_j}) \in E_j^{k_j}, \qquad 1 \le j \le J.
\]
The subsequences of $(X_1, \dots, X_I)$ formed by the terms in $E_1, \dots, E_{J}$ equal $y^{(1)}, \dots, y^{(J)}$ if and only if $I = k$ and $(X_1, \dots, X_k)$ is one of the $k!/(k_1! \cdots k_{J}!)$ sequences obtained by interleaving $y^{(1)}, \dots, y^{(J)}$. Each such sequence has probability $\prod_{j = 1}^{J} \prod_{i = 1}^{k_j} \nu(y^{(j)}_i)$, so the probability of this event is
\[
e^{-\mu} \frac{\mu^k}{k!} \cdot \frac{k!}{k_1! \cdots k_{J}!} \prod_{j = 1}^{J} \prod_{i = 1}^{k_j} \nu(y^{(j)}_i) = \prod_{j = 1}^{J} \bigg( e^{-\mu \nu(E_j)} \frac{(\mu \nu(E_j))^{k_j}}{k_j!} \prod_{i = 1}^{k_j} \frac{\nu(y^{(j)}_i)}{\nu(E_j)} \bigg),
\]
where we used that $\nu(E_1) + \dots + \nu(E_{J}) = 1$. The $j$-th factor on the right is the probability that a list of $\Pois(\mu \nu(E_j))$ independent elements of $E_j$ with law $\nu(\, \cdot \mid E_j)$ coincides with $y^{(j)}$. Since all lists take values in countable sets, (a) follows.

For (b), let $(f_i)_{i \ge 1}$ denote the edge process underlying $G^S(t)$. We apply (a) with $E$ the set of pairs of $S$, $\nu$ the uniform law, $X_i = f_i$, $I = \Pi_t$, and $\mu = t$. We partition $E$ into the pairs of $S'$, the pairs of $S_0$ (if $|S_0| \ge 2$), and, for each $a \in S_0$, the $|S'|$ pairs $\{a, x\}$ with $x \in S'$. The multigraph $G^S(t)[S']$ is formed by the subsequence of the pairs of $S'$, which is a list of $\Pois(t \binom{|S'|}{2}/\binom{N}{2})$ independent uniformly random pairs of $S'$. Let $\Pi'$ be an independent rate-one Poisson counting process, and set $s = t\binom{|S'|}{2}/\binom N2$. Then this is the law of the multigraph formed by the first $\Pi'_s$ terms of an edge process on $S'$.

The multigraph $G^S(t)[S_0]$ is a function of the subsequence of the pairs of $S_0$. The neighbor list of $a \in S_0$ in $S'$ is obtained from the subsequence of the pairs $\{a, x\}$ with $x \in S'$ by replacing each pair $\{a, x\}$ by $x$, and the uniform law on these pairs corresponds to the uniform law on $S'$. By (a), these subsequences are independent and have the stated laws, which proves (b).

To prove (c), we take $S_0 = \{a\}$ in (b), so that $|S'| = N - 1$, and we note that $\binom{N - 1}{2}/\binom{N}{2} = (N - 2)/N$ and $(N - 1)/\binom{N}{2} = 2/N$. The occurrences of $G^S(t)$ that contain $a$ are the pairs $\{a, x\}$ with $x$ an entry of the neighbor list of $a$ in $S \setminus \{a\}$, which gives the first two statements of (c).
\end{proof}

\Cref{lem:pre-split} is a special case of the restriction and marking theorems for Poisson processes; see \cite[Theorems~5.2, 5.6, and~5.8, Corollary~5.9]{last2018lectures}. We use it only at fixed times, and we have included the short computation for this case.

\section{Tail bounds}\label{sec:pre-tails}

We use the convention $0^0 = 1$. For $z \ge 0$ and integers $k \ge 0$, we define $\pi_z(k) = e^{-z} z^k/k!$. We also set $\pi_z(-1) = 0$. For $k \ge 0$, the value $\pi_z(k)$ is the probability that a $\Pois(z)$ random variable takes the value $k$. Inside a probability expression, we let $\Pois(z)$ denote a random variable with the Poisson law of mean $z$. We use the analogous convention for $\Bin(m, p)$. We will use the following elementary tail bounds.

\begin{lemma}\label{lem:pre-tails}
\begin{enumerate}[label=(\alph*)]
\item Let $X$ have the $\Bin(m, p)$ law, where $m \ge 1$ is an integer and $p \in [0, 1]$. For all integers $k \ge 1$, we have
\[
\Pp(X \ge k) \le \binom{m}{k} p^k \le \Big(\frac{e m p}{k}\Big)^k.
\]
\item Let $X$ have the $\Pois(\mu)$ law, where $\mu \ge 0$. For all real $k > \mu$, we have $\Pp(X \ge k) \le (e \mu/k)^k$.
\item Let $X$ have the $\Pois(\mu)$ law, where $\mu > 0$. For all real $t > 0$, we have
\[
\Pp(X \ge \mu + t) \le \exp\Big(-\frac{t^2}{2(\mu + t)}\Big), \qquad \Pp(X \le \mu - t) \le \exp\Big(-\frac{t^2}{2\mu}\Big).
\]
\item For all real $z \ge 0$ and integers $i \ge 1$, we have
\[
\Pp\big(\Pois(z) \ge i\big) \le (e^z - 1) \pi_z(i - 1).
\]
\end{enumerate}
\end{lemma}

\begin{proof}
We begin with (a), where we may assume $k \le m$, since otherwise the probability is zero. If $X \ge k$, then some set of $k$ of the $m$ trials consists of successes, and the union bound over these sets gives the first inequality. The second follows from $\binom{m}{k} \le m^k/k!$ and $k! \ge (k/e)^k$.

To prove (b) and (c), we use the Cram\'er--Chernoff method \cite[Section~2.2]{boucheron2013concentration}. If $\mu = 0$, then $X = 0$ and (b) holds. We now suppose that $\mu > 0$. We have $\E e^{\varphi X} = \exp(\mu (e^\varphi - 1))$ for every real $\varphi$. Applying Markov's inequality, we find that for $\varphi \ge 0$ and every real $x$,
\begin{equation}\label{eq:pre-chernoff}
\Pp(X \ge x) \le \exp\big(-\varphi x + \mu (e^\varphi - 1)\big).
\end{equation}
For (b), choosing $e^\varphi = k/\mu$ gives
\[
\Pp(X \ge k) \le e^{-\mu} \Big(\frac{e\mu}{k}\Big)^k \le \Big(\frac{e\mu}{k}\Big)^k.
\]

For the first bound in (c), we set $x = t/\mu$ and
\[
\psi(v) = (1 + v) \log(1 + v) - v, \qquad v > -1.
\]
Choosing $e^\varphi = 1 + x$ in \eqref{eq:pre-chernoff}, we obtain
\[
\Pp(X \ge \mu + t) \le \exp\big(-\varphi (\mu + t) + \mu (e^\varphi - 1)\big) = \exp\big(-\mu \psi(x)\big).
\]
Since $\psi(0) = 0$, $\psi'(0) = 0$, and $\psi''(v) = 1/(1 + v)$, we have
\[
\psi(x) = \int_0^x \frac{x - v}{1 + v} \dd v \ge \frac{1}{1 + x} \int_0^x (x - v) \dd v = \frac{x^2}{2(1 + x)},
\]
and therefore $\mu \psi(x) \ge t^2/(2(\mu + t))$.

For the second bound in (c), observe that the event is empty if $t > \mu$, and that its probability is $e^{-\mu} \le e^{-\mu/2}$ if $t = \mu$. Suppose that $0 < t < \mu$, and set $x = t/\mu \in (0, 1)$. For $\varphi \le 0$, Markov's inequality applied to $e^{\varphi X}$ gives
\[
\Pp(X \le \mu - t) \le \exp\big(-\varphi (\mu - t) + \mu (e^\varphi - 1)\big),
\]
and the choice $e^\varphi = 1 - x$ yields $\Pp(X \le \mu - t) \le \exp(-\mu \psi(-x))$, by the same computation. As before, we have
\[
\psi(-x) = \int_0^x \frac{x - v}{1 - v} \dd v \ge \int_0^x (x - v) \dd v = \frac{x^2}{2},
\]
so that $\mu \psi(-x) \ge t^2/(2\mu)$.

It remains to prove (d). Both sides vanish if $z = 0$. If $z > 0$, then
\[
\frac{\Pp(\Pois(z) \ge i)}{\pi_z(i - 1)} = \sum_{j \ge 1} \frac{z^j (i - 1)!}{(i - 1 + j)!} \le \sum_{j \ge 1} \frac{z^j}{j!} = e^z - 1,
\]
where we used that
\[
\frac{(i - 1 + j)!}{(i - 1)!} = \prod_{l = 1}^{j} (i - 1 + l) \ge j!. \qedhere
\]
\end{proof}

\section{Bounds on the quantiles}\label{sec:pre-centre}

We now bound the quantiles $L_n(\eta)$ and $U_n(\eta)$ from above and below. The upper bound is the first-moment bound. The lower bound rests on the classical fact that, for every fixed $c_0 \in (0, 1/2)$, with probability tending to one every component of $G(n, \lfloor c_0 n \rfloor)$ is a tree or has exactly one cycle \cite[Theorem~5e]{erdos1960evolution}. A quantitative form, proved by counting witness subgraphs, appears in \cite[Theorem~5.5 and its proof, pp.~112--113]{janson2000random}. We use the same witness types below, with a count adapted to our process, which samples pairs with replacement.

We will need the following lemma on cycles in multigraphs. For an integer $j \ge 0$, we define a \emph{path of length $j$} to consist of distinct vertices $v_0, \dots, v_j$ and distinct occurrences $p_1, \dots, p_j$ with $p_i = \{v_{i - 1}, v_i\}$. For an integer $j \ge 2$, we define a \emph{cycle of length $j$} to consist of distinct vertices $v_1, \dots, v_j$ and distinct occurrences $p_1, \dots, p_j$ with $p_i = \{v_i, v_{i + 1}\}$ for $i < j$ and $p_j = \{v_j, v_1\}$. (A cycle of length $2$ consists of two occurrences of the same pair.) We call a multigraph a \emph{theta} if it consists of three paths of lengths at least $1$ between the same two distinct end vertices, with no other vertices or occurrences in common. We call those two end vertices its \emph{branch vertices}. We call a multigraph a \emph{dumbbell} if it consists of two cycles without common occurrences, which either have exactly one common vertex, or have no common vertex and are joined by a path of length at least $1$ whose only vertices on the two cycles are its end vertices, one on each cycle. A theta or a dumbbell with $k$ vertices has $k + 1$ occurrences. For a multigraph $F$, we let $v(F)$ denote the number of vertices that lie in some occurrence of $F$, and $|F|$ the number of occurrences of $F$.

\begin{lemma}\label{lem:pre-cycles}
Let $F$ be a connected multigraph with at least two vertices.
\begin{enumerate}[label=(\alph*)]
\item If $|F| \le v(F)$, then $F$ is colorable.
\item If $|F| \ge v(F) + 1$, then $F$ contains a theta or a dumbbell.
\end{enumerate}
\end{lemma}

\begin{proof}
Let $\mathcal T$ be a spanning tree of $F$. It consists of $v(F) - 1$ occurrences of $F$, no two of them occurrences of the same pair. For an occurrence $p = \{x, y\}$ of $F$ outside $\mathcal T$, the occurrence $p$ and the path in $\mathcal T$ from $x$ to $y$ form a cycle of length at least $2$, and $p$ is the only occurrence of this cycle outside $\mathcal T$.

For (a), we use the assumption $q \ge 3$. If $|F| = v(F) - 1$, then $F = \mathcal T$ is a tree, which has a coloring with two colors. Otherwise, $F$ has exactly one occurrence $p$ outside $\mathcal T$, and we let $\mathcal C$ be the cycle formed by $p$ as above. The cycle $\mathcal C$ has a coloring with three colors.

We now extend this coloring to $F$. Since $\mathcal T$ is a tree and $p$ is the only occurrence of $F$ outside $\mathcal T$, the only occurrences of $F$ between vertices of $\mathcal C$ are those of $\mathcal C$. We color the remaining vertices in order of increasing distance in $\mathcal T$ from the vertex set of $\mathcal C$. Each vertex $y$ outside $\mathcal C$ is joined in $F$ to exactly one vertex that is colored before it, namely its neighbor on the path in $\mathcal T$ from $y$ to $\mathcal C$, since its other neighbors in $\mathcal T$ are farther from $\mathcal C$. We give $y$ a color different from the color of that neighbor, and we obtain a coloring of $F$.

We now prove (b). Let $p$ and $p'$ be two distinct occurrences of $F$ outside $\mathcal T$, and let $\mathcal C$ and $\mathcal C'$ be the cycles that they form. The only occurrence of $\mathcal C$ outside $\mathcal T$ is $p$, so $p'$ does not belong to $\mathcal C$.

Suppose first that $\mathcal C$ and $\mathcal C'$ have at most one common vertex. Then they have no common occurrence. If they have one common vertex, they form a dumbbell. If they have none, we let $\mathcal P$ be a shortest path in $F$ from a vertex of $\mathcal C$ to a vertex of $\mathcal C'$. By minimality, the only vertices of $\mathcal P$ on $\mathcal C$ or $\mathcal C'$ are its end vertices, and $\mathcal C$, $\mathcal C'$, and $\mathcal P$ form a dumbbell.

Suppose now that $\mathcal C$ and $\mathcal C'$ have at least two common vertices. We write the vertices of $\mathcal C'$ in cyclic order as $v_1, \dots, v_j$, with $p' = \{v_j, v_1\}$, and we let $i_1$ and $i_2$ be the smallest and the largest index $i$ such that $v_i$ is a vertex of $\mathcal C$. Then $i_1 < i_2$, and the path $v_{i_2}, v_{i_2 + 1}, \dots, v_j, v_1, \dots, v_{i_1}$ along $\mathcal C'$ contains $p'$, joins the distinct vertices $v_{i_2}$ and $v_{i_1}$ of $\mathcal C$, and has no other vertex on $\mathcal C$. Its occurrences are not occurrences of $\mathcal C$.

Indeed, $p'$ is not, and if the path has length at least $2$, then each of its occurrences contains a vertex outside $\mathcal C$. Together with the two paths along $\mathcal C$ between $v_{i_1}$ and $v_{i_2}$, this path forms a theta.
\end{proof}

\begin{lemma}\label{lem:pre-centre}
Let $\eta \in (0, 1/2]$.
\begin{enumerate}[label=(\alph*)]
\item Let $c_1 > \gamma_q$ be real, and let $n \ge 2q$ be an integer. We set
\[
C_{c_1} = \frac{q}{q - 1} e^{2c_1}.
\]
Then
\begin{equation}\label{eq:pre-first-moment}
\Pp\big(H > \lfloor c_1 n \rfloor\big) \le C_{c_1} \exp\Big(-n (c_1 - \gamma_q) \log \frac{q}{q - 1}\Big).
\end{equation}
For every $c_1 > \gamma_q$, we have $L_n(\eta) \le U_n(\eta) \le c_1 n$ for all large $n$. Moreover, $U_n(\eta) < M$ for all large $n$.
\item For every $c_0 \in (0, 1/2)$, there exists $C(c_0)$ such that $\Pp(H \le \lfloor c_0 n \rfloor) \le C(c_0)/n$ for all $n \ge 2q$. Further, $L_n(\eta) > c_0 n$ for all large $n$.
\end{enumerate}
\end{lemma}

\begin{proof}
We begin with (a). Let $\sigma \colon [n] \to [q]$ be a map. As in the proof of \cref{lem:pre-lifetime}(a), the fraction of pairs of $[n]$ on which $\sigma$ is constant is at least $(n/q - 1)/(n - 1)$. This implies that $\sigma$ is a coloring of the single occurrence $e_1$ with probability at most
\[
1 - \frac{n/q - 1}{n - 1} = \frac{q - 1}{q} \cdot \frac{n}{n - 1}.
\]
Since the pairs $e_i$ are independent, a union bound over the $q^n$ maps $\sigma$ gives, for all $m \ge 0$,
\begin{equation}\label{eq:pre-union}
\Pp(H > m) = \Pp(G_m \text{ is colorable}) \le q^n \Big(\frac{q - 1}{q}\Big)^m \Big(\frac{n}{n - 1}\Big)^m.
\end{equation}
We set $a = \log(q/(q - 1))$ and $m = \lfloor c_1 n\rfloor$. Then $\log q = \gamma_q a$ and $c_1 n - 1 < m \le c_1 n$. Taking logarithms in \eqref{eq:pre-union}, we find
\[
\begin{aligned}
\log \Pp(H > m) &\le n \gamma_q a - m a + \frac{m}{n - 1} \\
&\le n \gamma_q a - (c_1 n - 1) a + 2c_1 \\
&= -n (c_1 - \gamma_q) a + a + 2c_1,
\end{aligned}
\]
where we used $\log(n/(n - 1)) \le 1/(n - 1)$ and $m/(n - 1) \le 2c_1$ for $n \ge 2$. Since $e^{a} = q/(q - 1)$, this is \eqref{eq:pre-first-moment}.

To deduce the bounds on the quantiles, fix $c_1 > \gamma_q$. For every integer $m$ with $\lfloor c_1 n \rfloor < m \le M$, we have by \eqref{eq:pre-V-H} that
\[
\Pp(V \ge m) = \Pp(H > m) \le \Pp\big(H > \lfloor c_1 n \rfloor\big),
\]
and by \eqref{eq:pre-first-moment} the right side is smaller than $\eta$ for all large $n$. For such $n$, no integer $m > \lfloor c_1 n \rfloor$ belongs to the set that defines $U_n(\eta)$. Therefore $U_n(\eta) \le c_1 n$, and $L_n(\eta) \le U_n(\eta)$ by \cref{lem:pre-quantile}. To prove that $U_n(\eta) < M$, we set $c_1' = (\gamma_q + \Lambda)/2$. Then $c_1' > \gamma_q$ and $c_1' n < \lfloor\Lambda n\rfloor = M$ for all large $n$. We apply the preceding bound with this value of $c_1'$.

We now prove (b). Suppose that $G_m$ is not colorable. Then some connected component $F$ of $G_m$ is not colorable, and \cref{lem:pre-cycles}(a) implies that $|F| \ge v(F) + 1$. By \cref{lem:pre-cycles}(b), it follows that $G_m$ contains a theta or a dumbbell. We now count these multigraphs.

Let $k \ge 2$. A theta with $k$ vertices is determined by the lengths $j_1, j_2, j_3 \ge 1$ of its three paths, which satisfy $j_1 + j_2 + j_3 = k + 1$, together with the list of its two branch vertices followed by the interior vertices of the three paths in order. A dumbbell with $k$ vertices is determined by the lengths $j_1, j_2 \ge 2$ of its cycles and the length $j_3 \ge 0$ of the joining path, which satisfy $j_1 + j_2 + j_3 = k + 1$, together with a list of its vertices.

We list the vertices of the first cycle in cyclic order, starting from its attachment vertex. If $j_3 = 0$, the two attachment vertices coincide, and we next list the other $j_2 - 1$ vertices of the second cycle in cyclic order from that shared vertex. If $j_3 \ge 1$, we next list all $j_2$ vertices of the second cycle in cyclic order, starting from its attachment vertex, and finally the $j_3 - 1$ interior vertices of the joining path in order. In the first case the list has $j_1 + j_2 - 1 = k$ entries, and in the second it has $j_1 + j_2 + j_3 - 1 = k$ entries.

In both cases, the list consists of $k$ distinct elements of $[n]$, and two of the three lengths, each in $\{0, \dots, k + 1\}$, determine the third. There are at most $(k + 2)^2$ choices of lengths and at most $n^k$ lists. The number of multigraphs on $[n]$ that are thetas or dumbbells with $k$ vertices is therefore at most $2 (k + 2)^2 n^k$.

Let $F$ be one of these multigraphs, and let $p_1, \dots, p_{k + 1}$ denote its occurrences. If $F \subset G_m$, then there exist distinct indices $i_1, \dots, i_{k + 1} \le m$ with $e_{i_j} = p_j$ for all $j$. There are at most $m^{k + 1}$ choices of these indices, and for each choice this event has probability $\binom{n}{2}^{-(k + 1)}$, so that
\[
\Pp(F \subset G_m) \le \bigg(m \binom{n}{2}^{-1}\bigg)^{k + 1}.
\]

Now let $m \le c_0 n$, so that $m \binom{n}{2}^{-1} \le 2 c_0/(n - 1)$. A union bound over $k$ and $F$ gives
\[
\Pp(G_m \text{ is not colorable}) \le \sum_{k = 2}^n 2 (k + 2)^2 n^k \Big(\frac{2 c_0}{n - 1}\Big)^{k + 1} \le \frac{2 e^2}{n - 1} \sum_{k \ge 2} (k + 2)^2 (2 c_0)^{k + 1},
\]
where we used that for $k \le n$,
\[
\Big(\frac{n}{n - 1}\Big)^k \le \Big(1 + \frac{1}{n - 1}\Big)^n \le e^{n/(n - 1)} \le e^2.
\]
The last series converges since $2 c_0 < 1$. Taking $m = \lfloor c_0n\rfloor$ and using $1/(n - 1) \le 2/n$ gives the required bound. We define the constant by
\[
C(c_0) = 4 e^2 \sum_{k \ge 2} (k + 2)^2 (2 c_0)^{k + 1}.
\]

Finally, we fix $c_0' \in (c_0, 1/2)$. For all large $n$, we have $c_0 n + 1 \le c_0' n < M$. For such $n$ and every integer $m$ with $0 \le m \le c_0 n$, we have $m < M$, hence $\{V \le m\} = \{H \le m + 1\}$, and therefore
\[
\Pp(V \le m) = \Pp(H \le m + 1) \le \Pp\big(H \le \lfloor c_0' n \rfloor\big) \le \frac{C(c_0')}{n}.
\]
The right side is smaller than $\eta$ for all large $n$. For such $n$, no integer $m \le c_0 n$ belongs to the set that defines $L_n(\eta)$, so $L_n(\eta) > c_0 n$.
\end{proof}

The assumption $q \ge 3$ is needed in (b), since for $q = 2$ a component with exactly one cycle is not colorable when the cycle has odd length.