\chapter{Proof overview}\label{sec:overview}

\paragraph{Notation.}\label{sec:ov-notation}
We fix an integer $q \ge 3$ and write $\log$ for the natural logarithm. For integers $k \ge 1$, we set $[k] = \{1, \dots, k\}$. We write $\Pp$, $\E$, and $\Var$ for probability, expectation, and variance, and $\ind_A$ for the indicator of an event $A$; we also use $\ind\{ \cdot \}$ for the indicator of the condition in braces. For an event $A$ and a nonnegative or integrable expression $X$ defined on $A$, we define $\E[X; A]$ to be the integral of $X$ over $A$. When we write this as $\E[X\ind_A]$, we first extend $X$ by zero outside $A$. We write $\Pois(\mu)$ for the Poisson law with mean $\mu \ge 0$ and $\Bin(m, p)$ for the binomial law with integer $m \ge 0$ and $p \in [0, 1]$. Inside probability expressions, these symbols denote random variables with the specified laws. Constants may depend on $q$ and on fixed parameters named in a statement, but not on $n$; constants denoted by $C$ or $C'$ are local to their statements. We say \emph{for all large $n$} when a statement holds for every $n \ge n_0$, where $n_0$ depends only on those fixed parameters.

Our proof has four steps. Step 1 deduces a limiting threshold from a short interval containing the loss of colorability with high probability. Step 2 bounds the length of this interval through the expected number of further pair additions needed to destroy colorability of the last colorable graph. Step 3 bounds the advance of non-colorability under random vertex identification to treat final edges at vertices of low degree. Step 4 controls the growth of classes of vertices equal in every coloring to treat final edges at vertices of high degree. Steps 1 and 2 adapt the $k$-SAT arguments of \cite{carenini2026polynomial,openai2026limiting}; our new estimates in Steps 3 and 4 bound the expected lifetime of the last colorable graph at the final edge. In the $k$-SAT proofs, the corresponding estimate uses the variables that take the same value in every satisfying assignment and compares the clauses of length $k - 1$ left by deleting a variable with clauses of length $k$ \cite{carenini2026polynomial,openai2026limiting,openai2026variance}; this comparison has no direct analogue for colorings, since permuting the colors shows that no vertex has the same color in every coloring. The dependencies between these steps are recorded in \cref{fig:ov-dependencies}. Remarks labeled heuristic describe the motivation for the estimates.

\begin{figure}[t]
\centering
\input{figures/ov-dependencies}
\caption{The main steps of the proof. An arrow means that the first result is used to prove the second. The left branch is the low-degree estimate of \cref{sec:low}, and the right branch is the high-degree estimate of \cref{sec:high}. The convergence criterion is proved in \cref{app:conv}.}
\label{fig:ov-dependencies}
\end{figure}

We begin by defining the edge process. For a finite set $S$, we call a finite multiset of unordered pairs of distinct elements of $S$ a \emph{multigraph on $S$}, and we call its elements, counted with multiplicity, its \emph{occurrences}. We call a map $\sigma:S \to [q]$ a \emph{coloring} when the endpoints of every occurrence have different colors, and call the multigraph \emph{colorable} when there exists such a map. For a multigraph $G$ and a pair $e$ from its vertex set, we let $G + e$ denote the result of adding one occurrence of $e$; when $e$ occurs in $G$, we let $G - e$ denote the result of removing one occurrence. We define $\deg_G(u)$ to be the number of occurrences containing the vertex $u$. We call a uniformly chosen pair of distinct elements of the specified vertex set a \emph{uniform pair}.

Let $n \ge 2q$ be an integer. We let $e_1, e_2, \dots$ denote independent uniform pairs of $[n]$, and call this sequence the \emph{edge process}. For each integer $m \ge 0$, we define $G_m$ to be the multigraph consisting of the first $m$ occurrences of the process. We define $H$ to be the first $m$ for which $G_m$ is not colorable. We let $\cF_m$ denote the $\sigma$-algebra generated by $e_1, \dots, e_m$. The lifetime bound below implies that $H$ is finite almost surely. These definitions apply on other finite vertex sets when they are specified.

\section{Step 1: the window determines the threshold}\label{sec:ov-convergence}

We set $\gamma_q = \log q/\log(q/(q - 1))$. Throughout this overview, we take $\Lambda = \gamma_q + 2$ and set $M = \lfloor\Lambda n\rfloor$. We define $V$ to be the last colorable time capped at $M$ by setting $V = \min(H - 1, M)$. This makes $V$ a bounded function of $e_1, \dots, e_M$. For each $\eta \in (0, 1/2]$, we define $L_n(\eta)$ to be the smallest nonnegative integer $m$ with $\Pp(V \le m) \ge \eta$, and define $U_n(\eta)$ to be the largest integer $m \in \{0, \dots, M\}$ with $\Pp(V \ge m) \ge \eta$. We call $w_n(\eta) = U_n(\eta) - L_n(\eta)$ the \emph{window} at level $\eta$. These definitions give
\begin{equation}\label{eq:ov-quantiles}
\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}
Here the extrema are over nonnegative integers. By \cref{lem:pre-quantile}, $G_m$ is colorable with probability greater than $1 - \eta$ for $0 \le m \le L_n(\eta)$, and with probability smaller than $\eta$ for $U_n(\eta) < m \le M$. Applying \cref{lem:pre-centre}(b) with $c_0 = 1/4$ and part (a) with $c_1 = (\gamma_q + \Lambda)/2$, we have $n/4 < L_n(\eta) \le U_n(\eta) < M$ for all large $n$. The lower bound uses $q \ge 3$ to color components having at most one cycle.

We define $\eta_0$ to be the small quantile cutoff given by
\[
\eta_0 = \frac{e^{-2\Lambda}}8.
\]
We will use the following convergence criterion, proved in \cref{thm:red-convergence}. Let $(\delta_n)_{n \ge 1}$ be a nonincreasing sequence in $(0, 1]$ such that $\sum_{k \ge 1}\delta_{\lfloor e^k\rfloor} < \infty$. Suppose that, for all $\eta \in (0, \eta_0]$, there exists $K'(\eta) > 0$ such that
\begin{equation}\label{eq:ov-window-hyp}
w_n(\eta) \le K'(\eta) \, n \delta_n \qquad \text{for all large } n.
\end{equation}
Then there exists $\alpha_q \in [1/2, \gamma_q]$ such that $L_n(\eta)/n \to \alpha_q$ and $U_n(\eta)/n \to \alpha_q$ for all $\eta \in (0, \eta_0]$. For every fixed real $c \ge 0$ with $c \ne \alpha_q$,
\[
\lim_{n \to \infty}\Pp(H > \lfloor cn\rfloor) =
\begin{cases}
1 & \text{if } c < \alpha_q, \\
0 & \text{if } c > \alpha_q.
\end{cases}
\]
The same limits hold for the probability of colorability of a uniformly random simple graph on $[n]$ with $\lfloor cn\rfloor$ edges, and of a simple graph on $[n]$ in which each pair is an edge independently with probability $2c/n$. These models are defined for all sufficiently large $n$. In Steps 2--4, we prove \eqref{eq:ov-window-hyp} with $\delta_n = (\log n)^{-3/2}$ for $n \ge 3$ and $\delta_1 = \delta_2 = 1$. This sequence is admissible, since $\delta_{\lfloor e^k \rfloor} \le (k - 1)^{-3/2}$ for $k \ge 2$, which proves \cref{thm:intro-main}. For the error probability $\epsilon \in (0, 1)$ of \cref{thm:intro-window}, we set $\eta_1 = \min(\epsilon/2, \eta_0)$ and define $m_n = L_n(\eta_1)$. Using the window bound at level $\eta_1$, we get the stated concentration around $m_n$. The convergence criterion also implies that $m_n/n \to \alpha_q$, as shown in \cref{sec:proof-main}.

To prove \cref{thm:red-convergence}, we compare quantiles at different numbers of vertices through an auxiliary Poisson model. For every integer $n \ge 1$ and real $c \ge 0$, we let $A_n(c)$ denote the multiset formed by first sampling a $\Pois(cn)$ number of occurrences and, independently of that count, sampling ordered endpoints independently and uniformly in $[n] \times [n]$ for those occurrences. We call an occurrence whose two endpoints coincide a \emph{loop}. On a finite vertex set, we call a finite multiset of unordered pairs, allowing coincident endpoints, a \emph{multigraph with loops}. We require different colors at the endpoints of every occurrence; a loop prevents colorability. We let $\rho_n(c)$ denote the probability that $A_n(c)$ is colorable. \Cref{lem:conv-interp} states that
\begin{equation}\label{eq:ov-product}
\rho_{N_1 + N_2}(c) \ge \rho_{N_1}(c) \, \rho_{N_2}(c) \qquad \text{for all integers } N_1, N_2 \ge 1 \text{ and all } c \ge 0.
\end{equation}

Let $N = N_1 + N_2$, and set $S_1 = [N_1]$ and $S_2 = [N] \setminus [N_1]$. For a colorable multigraph $G$ on a finite vertex set and a vertex $u$, we define the \emph{frozen class} $C_G(u)$ to be the set of vertices that receive the same color as $u$ in every coloring, following \cite{culberson2001frozen}. For $0 \le \upsilon \le c$, we define $A^{(\upsilon)}$ to be the union of three independent families. These consist of $\Pois(N\upsilon)$ occurrences with independent uniform ordered endpoints in $[N]^2$, and, for $j = 1, 2$, $\Pois(N_j(c - \upsilon))$ occurrences with independent uniform ordered endpoints in $S_j^2$. The counts and endpoints are independent. We set $\chi(\upsilon) = \Pp(A^{(\upsilon)}\text{ is colorable})$. Adding an occurrence destroys colorability exactly when its endpoints lie in the same frozen class. On the event that $A^{(\upsilon)}$ is colorable, let $C_1, \dots, C_k$ denote its distinct frozen classes. We define the entire integrand below to be zero otherwise. Differentiating in the Poisson means, we find
\[
\chi'(\upsilon) = \E\!\left[\ind\{A^{(\upsilon)}\text{ is colorable}\}\sum_{i = 1}^k\left(\frac{|C_i \cap S_1|^2}{N_1} + \frac{|C_i \cap S_2|^2}{N_2} - \frac{|C_i|^2}{N}\right)\right].
\]
For each such class,
\begin{equation}\label{eq:ov-square}
\frac{|C_i \cap S_1|^2}{N_1} + \frac{|C_i \cap S_2|^2}{N_2} - \frac{|C_i|^2}{N_1 + N_2} = \frac{(N_2 |C_i \cap S_1| - N_1 |C_i \cap S_2|)^2}{N_1 N_2 (N_1 + N_2)} \ge 0.
\end{equation}
It follows that $\rho_N(c) = \chi(c) \ge \chi(0) = \rho_{N_1}(c)\rho_{N_2}(c)$. This is the coloring interpolation of \cite[Theorem~5 and Proposition~2]{bayati2013combinatorial}, in Poisson form as in \cite[Lemma~5.2]{openai2026limiting}.

Fix $\eta \in (0, \eta_0]$, and set $\xi_n = L_n(\eta)/n$ and $\Delta_n = \lceil\sqrt n\log n\rceil$. For $n \ge 2q$ and $c \ge 0$, let $J$ have the $\Pois(c(n - 1))$ law independently of $H$. Splitting loops from other occurrences gives
\[
\rho_n(c) = e^{-c}\Pp(H > J).
\]
For $0 < c \le \Lambda$, \cref{lem:conv-quantile}(b) gives, for all large $n$,
\[
\begin{aligned}
c(n - 1) \le L_n(\eta) - \Delta_n&\ \Longrightarrow\ \rho_n(c) \ge e^{-\Lambda}(1 - \eta)(1 - e^{-(\log n)^2/(2\Lambda)}), \\
c(n - 1) \ge U_n(\eta) + \Delta_n&\ \Longrightarrow\ \rho_n(c) \le \eta + e^{-(\log n)^2/(2\Lambda)}.
\end{aligned}
\]
For large integers $N_1, N_2$, we apply these comparisons at sizes $N_1, N_2, N = N_1 + N_2$ with
\[
c = \min_{j \in \{1, 2\}}\left(\xi_{N_j} - \frac{2\Delta_{N_j}}{N_j}\right).
\]
By the product inequality, we have $\rho_N(c) > e^{-2\Lambda}/2 > 2\eta$. The upper comparison then forces $c(N - 1) < U_N(\eta) + \Delta_N$. We can now use the bound on $w_N(\eta)$ to bound the lower quantile. For real $u \ge 1$, we define $g(u) = K'(\eta)\delta_{\lfloor u\rfloor} + (\Lambda + 6)(\log u)/\sqrt u$. By \Cref{lem:conv-superadd}, for all sufficiently large integers $N_1, N_2$, we have
\begin{equation}\label{eq:ov-superadd}
\xi_{N_1 + N_2} \ge \min(\xi_{N_1}, \xi_{N_2}) - g\bigl(\min(N_1, N_2)\bigr), \qquad \xi_{N_1 + 1} \ge \xi_{N_1} - g(N_1).
\end{equation}
For the adjacent-size inequality, we apply the product inequality with $N_2 = 1$ and $c = \xi_{N_1} - 2\Delta_{N_1}/N_1$, using $\rho_1(c) = e^{-c}$. This is a separate one-vertex comparison; the preceding large-size hypothesis does not allow direct substitution of $N_2 = 1$.

Fix a sufficiently large integer $\ell$ and an integer $n \ge \ell^2$. We write $n$ as a sum of blocks of sizes $\ell$ and $\ell + 1$. We form a binary tree by repeatedly dividing each collection of blocks into two collections whose numbers of blocks differ by at most one. At each internal node, we apply the first inequality of \eqref{eq:ov-superadd} with $(N_1, N_2)$ equal to the total vertex counts in its two children. For a leaf of size $\ell + 1$, we use the second inequality with $N_1 = \ell$. Along each path toward the root, the vertex counts grow by a factor of at least $4/3$. The function $g$ is positive, nonincreasing on $[e^2, \infty)$, and satisfies $\sum_{k \ge 1}g(e^k) < \infty$. Applying \cref{lem:conv-tree} to this $g$, this sequence $(\xi_n)$, and $u_0 = e^2$, we find
\begin{equation}\label{eq:ov-tree}
\xi_n \ge \xi_\ell - g(\ell) - \sum_{i \ge 1} g\Bigl(\frac{\ell}{4} \Bigl(\frac{4}{3}\Bigr)^i\Bigr) \qquad \text{for all } n \ge \ell^2.
\end{equation}
The right side differs from $\xi_\ell$ by an amount that tends to zero as $\ell \to \infty$, since $\sum_k g(e^k) < \infty$. We conclude that $\liminf_n \xi_n \ge \limsup_\ell \xi_\ell$, and $\xi_n$ converges. The summability condition is essential for this convergence argument: \cref{rem:conv-necessity} constructs a bounded, nonconvergent sequence satisfying the same comparisons with a nonsummable error. In particular, a window of order $n/\log n$ would not suffice for this argument.

Finally, for $0 < \eta_- < \eta_+ \le \eta_0$ we have $L_n(\eta_-) \le L_n(\eta_+) \le U_n(\eta_-)$. All levels therefore share one limit $\alpha_q$. Letting $\eta \to 0$ after $n \to \infty$, we get the zero-one law for $\Pp(H > \lfloor cn \rfloor)$, and we apply \cref{lem:conv-transfer}(a) with $m = \lfloor cn\rfloor$ for each fixed $0 \le c < \Lambda$; larger $c$ follow by monotonicity. For a fixed $d \ge 0$, in part (b) we set $p = d/n$ and $m = \lfloor cn\rfloor$, choosing $d/2 < c < \alpha_q$ below the threshold and $\alpha_q < c < d/2$ above it. These substitutions give \cref{thm:intro-main}. Since the window bound holds at every small level, we do not need the sharp threshold theorem of Achlioptas and Friedgut (see \cref{rem:red-af}). This step adapts \cite[Section~5]{openai2026limiting}, which compares expectations rather than quantiles and has polynomially small errors. Summable errors appear in the classical theory of nearly superadditive sequences \cite[Theorem~23]{debruijn1952some}, \cite[arXiv:1006.3786v1, Section~4.3, Lemma~8 and Remark~3]{abbe2014concentration}.

\section{Step 2: the window and the last colorable graph}\label{sec:ov-lifetime}

We fix $\eta \in (0, \eta_0]$. We write $L$, $U$, and $w$ for $L_n(\eta)$, $U_n(\eta)$, and $w_n(\eta)$, respectively. We call $\Gamma = G_{H - 1}$ the \emph{last colorable graph} and call $e_H$ the \emph{final edge}. For a multigraph $G$ on a finite set with at least two vertices, we define $T_G$ to be the number of independent uniform pair additions on that same vertex set needed to destroy colorability, counting the destroying addition and taking $T_G = 0$ if $G$ is already not colorable and $T_G = \infty$ if no addition destroys colorability. For integers $b \ge 0$, we define the \emph{expected lifetime} and its cap by
\[
r(G) = \E T_G, \qquad r_b(G) = \E\min(T_G, b).
\]

We define $Y = \min(U, \max(L, V))$ to be $V$ clipped to the interval $[L, U]$. Then
\[
Y = \min(U, \max(L, V)) = L + \sum_{m = L + 1}^{U} \ind\{G_m \text{ is colorable}\}.
\]
For $1 \le i \le U$, we define $Y^{(-i)}$ by the same sum with $e_i$ omitted from every $G_m$ and all remaining indices unchanged. The omission form of the Efron--Stein inequality \cite[(3.6)]{boucheron2005moment} states that, for a square-integrable function $Z$ of independent random variables $X_1, \dots, X_U$ and square-integrable functions $Z_i$ of the coordinates other than $X_i$, we have
\[
\Var(Z) \le \sum_{i = 1}^U \E[(Z - Z_i)^2].
\]
The variables $Y$ and $Y^{(-i)}$ are bounded functions of the required coordinates. Substituting $X_i = e_i$, $Z = Y$, and $Z_i = Y^{(-i)}$ gives
\[
\Var(Y) \le \sum_{i = 1}^U\E[(Y^{(-i)} - Y)^2].
\]
We evaluate this sum exactly in \Cref{lem:red-deletion}:
\begin{equation}\label{eq:ov-deletion}
\sum_{i = 1}^{U} \E\bigl[(Y^{(-i)} - Y)^2\bigr] = \E\bigl[H \bigl(2 r_{U - H + 1}(\Gamma) - 1\bigr); L < H \le U\bigr].
\end{equation}

The difference $Y^{(-i)} - Y$ counts the times $m \in (L, U]$ at which $G_m$ is not colorable but $G_m$ without the occurrence $e_i$ is colorable. We call a pair $\{u, v\}$ of distinct vertices a \emph{frozen pair} of a colorable multigraph $G$ if $u$ and $v$ lie in the same frozen class. For a colorable multigraph $G$ on a finite vertex set $S$ with $|S| \ge 2$, we define $\kappa(G)$ to be the number of its frozen pairs divided by $\binom{|S|}{2}$. We set $\kappa(G) = 0$ if $G$ is not colorable. Conditionally on the other occurrences up to time $m$, the occurrence $e_i$ is a uniform pair that makes their multigraph $G$ non-colorable with probability $\kappa(G)$. The number of later times at which the difference persists is governed by an independent continuation of $G$, which leads to the weight $2r_{U - m + 1}(G) - 1$ after squaring. The factor $H$ comes from exchangeability.

For every nonnegative function $h$ on multigraphs on $[n]$ and every integer $m \ge 0$, we have the terminal identity
\begin{equation}\label{eq:ov-terminal}
\E\bigl[h(\Gamma); H = m + 1\bigr] = \E\bigl[\kappa(G_m) h(G_m)\bigr].
\end{equation}

More generally, let $\cE$ be a set of pairs $(G, e)$ with $G$ a colorable multigraph on $[n]$ and $e$ a frozen pair of $G$. We define $\kappa_\cE(G)$ to be the fraction of all pairs $e$ for which $(G, e) \in \cE$. For this restriction on the edge, the identity becomes
\[
\E[h(\Gamma);H = m + 1, \ (\Gamma, e_H) \in \cE]
= \E[\kappa_\cE(G_m)h(G_m)].
\]
Taking $\cE$ to contain all frozen pairs gives \eqref{eq:ov-terminal}. By \cref{lem:pre-hazard,lem:pre-terminal}, this identity follows from the fact that $\Pp(H = m + 1 \mid \cF_m) = \kappa(G_m)$. We will use \eqref{eq:ov-terminal} repeatedly, also for final edges of a prescribed kind, to convert statements about $\Gamma$ into statements about the graphs $G_m$ at deterministic times. This step follows the deletion argument of \cite[Lemmas~3.1 and~3.2]{openai2026limiting}, and the role of the lifetime of the last state goes back to Aldous \cite[Theorem~1(b)]{aldous1991threshold} and its application by Carenini \cite[Theorem~4.1]{carenini2026polynomial}. The related argument with weighted deletion appears in \cite[Section~3.3, Lemma~3.4]{openai2026variance}; see \cref{sec:intro-related}.

\Cref{lem:red-varlower} uses an independent copy of $Y$ to show that $\Var(Y) \ge \Pp(Y = L) \Pp(Y = U) w^2 \ge \eta^2 w^2$. On the event $\{L < H \le U\}$, we have $r_{U - H + 1}(\Gamma) \le \min(w, r(\Gamma))$. Inserting this into \eqref{eq:ov-deletion}, we find
\begin{equation}\label{eq:ov-window-lifetime}
\eta^2 w^2 \le \Var(Y) \le 2U \, \E\bigl[\min(w, r(\Gamma)); L < H \le U\bigr].
\end{equation}
To bound the window, it suffices to bound the expected lifetime at final edges inside it. We set $\eps_n = (\log n)^{-3/2}$ for $n \ge 3$ and $\eps_1 = \eps_2 = 1$, and define $x_n = n\eps_n^2$. In the present range $n \ge 2q$, we have $x_n = n(\log n)^{-3}$. For every constant $K_0 \ge 0$, we have by \cref{prop:red-window}
\[
\E[\min(n\eps_n, r(\Gamma));L < H \le U] \le K_0n\eps_n^2
\quad\Longrightarrow\quad
w \le \max(1, 2\Lambda K_0/\eta^2)n\eps_n.
\]
Since
\[
\min(n\eps_n, r(\Gamma)) \le x_n + n\eps_n\ind\{r(\Gamma) > x_n\},
\]
it suffices to prove
\begin{equation}\label{eq:ov-target}
\Pp\bigl(L < H \le U, \ r(\Gamma) > x_n\bigr) \le 2 \eps_n,
\end{equation}
and \cref{prop:red-split} gives the conclusion with $K_0 = 3$.

However, the elementary lifetime bound for a single graph does not give \eqref{eq:ov-target}. For a colorable multigraph $G$ on $[n]$, waiting for a uniform pair that is a frozen pair gives $\kappa(G) \le 1/r(G)$ by \cref{lem:pre-lifetime}. We apply \eqref{eq:ov-terminal} with $h(G) = \ind\{r(G) > x_n\}$ and sum over $L \le m < U$. Since $\kappa(G)r(G) \le 1$, each such time contributes at most $1/x_n$ to the left side of \eqref{eq:ov-target}, and summing over the $M$ times up to the cap gives only the bound $M/x_n \approx \Lambda (\log n)^3$, which is far too large. We instead bound the sums over time directly in Steps 3 and 4. We set $D_n = \lfloor(\log n)^{1/4}\rfloor$. We call an endpoint \emph{low-degree} if its degree in $\Gamma$ is at most $D_n$, and \emph{high-degree} otherwise. We split according to these degrees and prove that, for all large $n$,
\begin{align}
\Pp\Bigl(H < \infty, \ \min_{v \in e_H} \deg_\Gamma(v) \le D_n, \ r(\Gamma) > x_n\Bigr) &\le \eps_n, \label{eq:ov-low} \\
\Pp\Bigl(H \le M, \ \max_{v \in e_H} \deg_\Gamma(v) > D_n\Bigr) &\le \eps_n. \label{eq:ov-high}
\end{align}
These are \cref{cor:low,thm:high-main}. Each final edge in the event of \eqref{eq:ov-target} belongs to one of these events, since $U \le M$. The estimates hold uniformly over the location of the window, which is not known in advance. The first concerns final edges at all times, and the second concerns all final edges up to time $M$, without any restriction on the lifetime. Together with \cref{prop:red-split}, they give $w_n(\eta) \le (6\Lambda/\eta^2) \, n (\log n)^{-3/2}$ for all large $n$, which is \cref{thm:proof-window}.

\section{Step 3: final edges at a vertex of low degree}\label{sec:ov-low}

We now explain the proof of \eqref{eq:ov-low}. \Cref{thm:low-main} shows that there exists $C_{\rm low} > 0$, depending only on $q$, such that for all large $n$ and all $y > 0$,
\begin{equation}\label{eq:ov-low-main}
\Pp\Bigl(H < \infty, \ \min_{v \in e_H} \deg_\Gamma(v) \le D_n, \ r(\Gamma) > y\Bigr) \le C_{\rm low} y^{-1/2} n^{3/8},
\end{equation}
and with $y = x_n$ the right side is $C_{\rm low} (\log n)^{3/2} n^{-1/8}$, which is smaller than $\eps_n$ for all large $n$.

We use the restriction on the lifetime to bound the sizes of the frozen classes. We set $A_q = 2q\log q + 2q + 1$. For a colorable multigraph $G$ on $[n]$, we have $\kappa(G)r(G) \le 1$ and $r(G) \le A_qn$ by \Cref{lem:pre-lifetime}. Applying \cref{lem:pre-classmass} with vertex set $[n]$ and size $n \ge 2q$, we get the following bound whenever $y > 0$ and $r(G) > y$. Let $C_1, \dots, C_k$ denote the frozen classes of $G$.
\begin{equation}\label{eq:ov-classmass}
\max_{1 \le i \le k} \frac{|C_i|^2}{n^2} \le \sum_{i = 1}^k \frac{|C_i|^2}{n^2} = \Bigl(1 - \frac{1}{n}\Bigr) \kappa(G) + \frac{1}{n} \le \frac{1 + A_q}{r(G)} < \frac{1 + A_q}{y},
\end{equation}
so every frozen class of $G$ has at most $n((1 + A_q)/y)^{1/2}$ elements. For each low-degree endpoint of a frozen pair in $\Gamma$, the number of possible partners is one less than the size of its frozen class. In the edge-restricted terminal identity, we take $\cE$ to contain the frozen pairs with an endpoint of degree at most $D_n$, take $h(G) = \ind\{r(G) > y\}$, and sum over all $m \ge 0$. We let $(\Pi_t)_{t \ge 0}$ denote a Poisson counting process of rate one, independent of the pairs and define $G(t) = G_{\Pi_t}$ for $t \ge 0$; we call this the \emph{Poissonized process}. On any other finite vertex set, the same term means the edge process evaluated at an independent Poisson clock of rate one. Applying \cref{lem:pre-poisson} with $\theta = 1$ to the resulting nonnegative function of $G_m$, and using invariance under vertex relabeling, reduces the bound to a fixed vertex. We set $a_0 = n$. We bound the left side of \eqref{eq:ov-low-main} by $(2n/(n - 1))((1 + A_q)/y)^{1/2}$ times
\begin{equation}\label{eq:ov-low-occupation}
\int_0^\infty \Pp\bigl(\deg_{G(t)}(a_0) \le D_n \text{ and } a_0 \text{ lies in a frozen pair of } G(t)\bigr) \dd t.
\end{equation}
It remains to show that this integral, the expected total time that $a_0$ spends in a frozen pair while $\deg_{G(t)}(a_0) \le D_n$, is $O(n^{3/8})$.

Let $G$ be a colorable multigraph on $[n]$, and let $a, b \in [n]$ be distinct vertices in one frozen class. We define $B$ to be the multigraph on $[n] \setminus \{a\}$ formed by the occurrences not containing $a$, and define a \emph{list} to be a finite sequence. We let $\mathbf x$ denote the list of the other endpoints of occurrences containing $a$, counting repetitions, and call it a \emph{neighbor list} of $a$ in $G$. If a coloring of $B$ left two colors unused on this list, it would extend to two colorings of $G$ agreeing at $b$ and disagreeing at $a$. For each coloring $\sigma$ of $B$, we therefore have
\[
b \in C_G(a) \setminus \{a\}
\quad\Longrightarrow\quad
\bigl|\{\sigma(v):v\text{ is an entry of }\mathbf x\}\bigr| \ge q - 1 \ge 2.
\]
We call a list \emph{never monochromatic} in a colorable multigraph if no coloring of that multigraph gives the same color to all entries of the list; a coloring is constant on an empty list by convention. The displayed inequality says that $\mathbf x$ is never monochromatic in $B$. This is the only use of $q \ge 3$ in the window estimates. For $q = 2$, take distinct vertices $a, v, b$ and define a graph by the edges $\{a, v\}$ and $\{v, b\}$. It forces equal colors at $a, b$, but its one-entry neighbor list $(v)$ is constant in every coloring.

For a multigraph $B$ on a finite set and a nonempty subset $Z$ of that set, we define $B/Z$ by replacing all vertices of $Z$ by one new vertex in every occurrence, preserving multiplicity and retaining occurrences internal to $Z$ as loops. We apply \cref{lem:low-frozen}(iv) with $F = B$. By the classical correspondence for identification \cite[Section~3, Theorem~1]{read1968introduction}, we have
\[
B/Z\text{ is colorable}\quad\Longleftrightarrow\quad
\text{some coloring of }B\text{ is constant on }Z.
\]
Taking $Z$ to be the set of entries of $\mathbf x$, we conclude that $B/Z$ is not colorable.

We call the multigraph on $[n - 1]$ formed by the occurrences of $G(t)$ not containing $a_0$ the background graph at time $t$. We let $\mathbf x$ denote the neighbor list of $a_0$ at time $t$. We apply \cref{lem:pre-split}(c) with $S = [n]$ and $a = a_0 = n$, using Poisson splitting \cite[Theorems~5.2 and~5.8]{last2018lectures}. Before conditioning on the event in \eqref{eq:ov-low-occupation}, the background graph and this list are independent. The background graph has the law of the Poissonized process on $[n - 1]$ at time $(n - 2)t/n$, and the list has a $\Pois(2t/n)$ length and, conditional on its length, independent uniform entries in $[n - 1]$. Conditional on a list length at most $D_n$, we enlarge its set of entries by choosing $D_n$ minus the number of distinct entries uniformly from the complement. The resulting set $Z$ has an unconditionally uniform law among the $D_n$-subsets, by invariance under relabeling, and is independent of the background graph. The property of being never monochromatic persists under enlargement. We now let $(B_m)_{m \ge 0}$ denote the time-$m$ graphs of a fresh edge process on $[n - 1]$, independent of a uniform $D_n$-subset $Z$. We define $H^{(n - 1)}$ and $H_Z$ to be the first non-colorable indices of $B_m$ and $B_m/Z$, respectively. By this equivalence, we have
\[
H^{(n - 1)} - H_Z = \sum_{m \ge 0}\ind\{B_m\text{ is colorable}, \ B_m/Z\text{ is not colorable}\}.
\]
We apply \cref{lem:pre-poisson} on $[n - 1]$ with $\theta = (n - 2)/n$ to the function assigning a colorable graph the probability that an independent uniform $D_n$-subset destroys colorability on identification, and assigning zero otherwise. We find
\begin{equation}\label{eq:ov-to-identify}
\int_0^\infty \Pp\bigl(\deg_{G(t)}(a_0) \le D_n \text{ and } a_0 \text{ lies in a frozen pair of } G(t)\bigr) \dd t \le \frac{n}{n - 2} \E\bigl[H^{(n - 1)} - H_Z\bigr].
\end{equation}
The right side is $n/(n - 2)$ times the expected advance of non-colorability caused by identifying $D_n$ random vertices.

\Cref{prop:low-identify} bounds this advance. Let $N \ge \lceil4q\log q\rceil + 1$ and $1 \le D \le N/4$ be integers. We set $z_0 = 4q\log q + 1$ and $C_q = 2e^{z_0}$, and let $k > eDz_0$ be an integer. In this comparison, we use $(B_m)_{m \ge 0}$ for the time-$m$ graphs of an edge process on $[N]$. We take $Z$ to be an independent uniform $D$-subset of $[N]$, and define $H^{(N)}$ and $H_Z$ as the first non-colorable indices of $B_m$ and $B_m/Z$. Then
\begin{equation}\label{eq:ov-identify}
\E\bigl[H^{(N)} - H_Z\bigr] \le C_q \Bigl(D^k + N \Bigl(\frac{e D z_0}{k}\Bigr)^k + D^2 + 1\Bigr).
\end{equation}
For all sufficiently large $n$, we set $k_n = \lceil\log n/\log\log n\rceil$ and apply \eqref{eq:ov-identify} with $(N, D, k) = (n - 1, D_n, k_n)$. These values satisfy its integer, size, and truncation hypotheses, and
\[
D_n^{k_n} \le n^{1/4}(\log n)^{1/4}, \qquad
(n - 1)\left(\frac{eD_nz_0}{k_n}\right)^{k_n} \le n^{3/8}.
\]
Using $D_n^2 \le (\log n)^{1/2}$, we get
\[
\E[H^{(n - 1)} - H_Z] \le 2C_qn^{3/8}.
\]
Together with the class-mass bound, the reduction to \eqref{eq:ov-low-occupation}, and \eqref{eq:ov-to-identify}, this proves \eqref{eq:ov-low-main}.

To prove \eqref{eq:ov-identify}, we compare the lists of neighbors before and after identification. After Poissonizing the edge process on $[N]$, we bound the part of the time integral beyond $2q(\log q)N$ by $2q$. Fix $0 \le s \le 2q(\log q)N$ and a set of $D$ vertices to identify. We call the multigraph of occurrences internal to the remaining $N - D$ vertices the background graph. Its pair counts are independent with law $\Pois(s/\binom N2)$. We define $\hat z$ to be the mean length of each neighbor list from an identified vertex into the remaining set. By Poisson splitting, we have
\[
\hat z = \frac{(N - D)s}{\binom N2} \le z_0.
\]
The neighbor lists have independent $\Pois(\hat z)$ lengths, conditionally independent uniform entries in the remaining set, and are independent of the background graph. Occurrences internal to the identified set contribute $O_q(D^2)$ to the time integral. In their absence, identification gives the background graph together with a new vertex whose neighbor list has $\Pois(D\hat z)$ independent uniform entries.

For comparison, replace the new vertex's neighbor list by an independent list of $\Pois(\hat z)$ uniform entries of the remaining set. We define $F(t)$ to be the Poissonized process on the remaining $N - D$ vertices together with that new vertex, and set $\lambda' = \binom{N - D + 1}{2}/\binom N2$. The resulting graph has the law of $F(\lambda's)$. We apply \cref{lem:low-added} at the same time $s$ with the explicit substitutions
\[
\begin{gathered}
V' = \text{remaining vertex set}, \quad N' = N - D, \quad o = \text{new vertex}, \\
\lambda = 1/\tbinom N2, \quad B' = \text{background graph}.
\end{gathered}
\]
It bounds the probability that this replacement list destroys colorability of a colorable background graph by $(e^{\hat z} - 1)\E\kappa(F(\lambda's))$. Since the process loses colorability at most once, we can integrate the probability that one further edge destroys colorability to get
\[
\int_0^\infty\E\kappa(F(\lambda's))\,\dd s \le \frac1{\lambda'} \le \frac{16}{9}.
\]
We use the convention $0^0 = 1$. For $z \ge 0$ and integers $j \ge 0$, we define $\pi_z(j) = e^{-z}z^j/j!$. To compare the two list lengths, we use
\begin{equation}\label{eq:ov-tilt}
\pi_{D\hat z}(j) = D^j e^{-(D - 1)\hat z}\pi_{\hat z}(j) \le D^k\pi_{\hat z}(j)\qquad\text{for integers }0 \le j \le k.
\end{equation}
We bound the probability that the identified vertex has more than $k$ neighbors by $(eDz_0/k)^k$. Together with \eqref{eq:ov-tilt}, this accounts for the terms in \eqref{eq:ov-identify} from the length comparison, long lists, occurrences inside the identified set, and large times. The limitation of this comparison is quantified in \cref{rem:low-limit}: at degree of order $\sqrt{\log n}$, its two principal terms cannot both be $o(\sqrt n)$, whereas the factor $((1 + A_q)/y)^{1/2}$ used before \eqref{eq:ov-low-occupation} is of order $n^{-1/2}(\log n)^{3/2}$ at $y = x_n$. This explains why we use a different argument for the remaining degrees.

\section{Step 4: final edges at vertices of high degree}\label{sec:ov-high}

We now prove \eqref{eq:ov-high}. For a colorable multigraph $G$ on $[n]$ and an integer $j \ge 0$, we define $\kappa_j(G)$ to be the number of ordered pairs $(u, v)$ of distinct vertices in one frozen class, which we call \emph{ordered frozen pairs}, with $\deg_G(u) = j$, divided by $n(n - 1)$. We set $\kappa_j(G) = 0$ for non-colorable $G$. In the edge-restricted terminal identity, we take $\cE$ to contain the frozen pairs with an endpoint of degree greater than $D_n$, take $h = 1$, and sum over $0 \le m < M$. Counting each eligible unordered pair through at least one of its endpoints gives
\[
\Pp(H \le M, \ \max_{v \in e_H}\deg_\Gamma(v) > D_n)
\le 2\sum_{m = 0}^{M - 1}\sum_{j = D_n + 1}^{m}\E\kappa_j(G_m).
\]
The identification estimate above does not cover all these degrees. We instead delete occurrences. For a colorable $G$ and an ordered frozen pair $(u, v)$, we call an occurrence $e$ containing $u$ \emph{non-pivotal} if the pair remains frozen in $G - e$, and \emph{pivotal} otherwise. We set $K = \lceil8\Lambda\rceil$. We define $\kappa_j^{\rm piv}(G)$ by restricting the count in $\kappa_j(G)$ to pairs for which at most $K - 1$ occurrences at $u$ are non-pivotal, and set it to zero for non-colorable $G$.

Let $f$ be a uniform pair independent of the process. For integers $1 \le i \le m$, the pair $(G_m - e_i, e_i)$ has the law of $(G_{m - 1}, f)$; this is the analogue of the Mecke equation for a fixed number of independent points \cite[Theorem~4.1]{last2018lectures}. Deleting one of at least $K$ occurrences at $u$ that are non-pivotal for $(u, v)$ leaves $u$ and $v$ in one frozen class and lowers the degree of $u$ by one. A uniform pair contains $u$ with probability $2/n$. Using \cref{lem:high-deletion}(a), we find
\begin{equation}\label{eq:ov-descent}
\E \kappa_j(G_m) \le \E \kappa_j^{\rm piv}(G_m) + \frac{2m}{nK} \E \kappa_{j - 1}(G_{m - 1}) \le \E \kappa_j^{\rm piv}(G_m) + \frac{1}{4} \E \kappa_{j - 1}(G_{m - 1})
\end{equation}
for $1 \le j \le m \le M$, where we used $m \le M \le \Lambda n$ and $K \ge 8\Lambda$. Let $w_0 = \lfloor D_n/2 \rfloor$. Iterating \eqref{eq:ov-descent} from the degree $j$ down to $w_0$, we find that for $w_0 < j \le m < M$,
\begin{equation}\label{eq:ov-iterate}
\E \kappa_j(G_m) \le \sum_{j' = w_0 + 1}^{j} 4^{-(j - j')} \E \kappa_{j'}^{\rm piv}(G_{m - j + j'}) + 4^{-(j - w_0)} \E \kappa_{w_0}(G_{m - j + w_0}).
\end{equation}
Summing \eqref{eq:ov-terminal} with $h = 1$ over $m$ shows that $\sum_m \E \kappa(G_m) \le 1$, since the process becomes non-colorable at most once. Therefore the last terms in \eqref{eq:ov-iterate} contribute at most $(8/3) 4^{-(D_n + 1 - w_0)}$. It remains to bound the pivotal terms, whose degrees exceed $w_0$.

If a pivotal occurrence for $(u, v)$ joins $u$ to a vertex $y$, deleting it separates $u$ and $v$ into different frozen classes. Adding it back merges those classes. For the rest of this step, we fix a vertex $u \in [n]$ and call it the \emph{root}. For a colorable multigraph $G$ on $[n]$, we set $W = [n] \setminus C_G(u)$. We define $R_G(u)$ to be the set of ordered pairs $(y, v) \in W^2$ such that every coloring gives $u$ the color of $y$ or of $v$. We define its density $\beta_G(u) = |R_G(u)|/n^2$. For every $y \in [n]$, we define the \emph{section} $R_G(u;y) = \{v \in [n]:(y, v) \in R_G(u)\}$. When $G$ and $u$ are fixed, we write $R(y)$ for $R_G(u;y)$. We set $R_G(u) = \emptyset$ and $\beta_G(u) = 0$ when $G$ is not colorable. Thus
\begin{equation}\label{eq:ov-relation}
\begin{gathered}
R_G(u) = \bigl\{(y, v) \in W \times W : \sigma(u) \in \{\sigma(y), \sigma(v)\} \text{ for every coloring } \sigma \text{ of } G\bigr\}, \\
\beta_G(u) = \frac{|R_G(u)|}{n^2}, \qquad R(y) = \{v : (y, v) \in R_G(u)\}.
\end{gathered}
\end{equation}
The relation is symmetric. For $y \in W$, \cref{lem:high-relation} shows that $G + \{u, y\}$ is colorable and
\begin{equation}\label{eq:ov-section}
C_{G + \{u, y\}}(u) = C_G(u) \cup R(y) \qquad \text{for all } y \in W.
\end{equation}
Indeed, the colorings of $G + \{u, y\}$ are the colorings $\sigma$ of $G$ with $\sigma(y) \ne \sigma(u)$, and for $v \in W$, all of them satisfy $\sigma(v) = \sigma(u)$ if and only if $(y, v) \in R_G(u)$. Hence $n \beta_G(u)$ is the average of $|R(y)|$ over $y \in [n]$, and for $y \in W$, the number $|R(y)|$ counts the vertices that join the frozen class of $u$ when $\{u, y\}$ is added. Note that a pair counted in $\kappa_j^{\rm piv}(G_m)$ has at least $j - K + 1$ pivotal occurrences at $u$. Deleting one of them and using exchangeability as before, we get the following bound from \cref{lem:high-deletion}(b) for integers $m \ge 1$, $j \ge K$, and all $u \in [n]$:
\begin{equation}\label{eq:ov-pivotal}
\E \kappa_j^{\rm piv}(G_m) \le \frac{2mn}{(n - 1)^2 (j - K + 1)} \, \E\bigl[\ind\{\deg_{G_{m - 1}}(u) = j - 1\} \beta_{G_{m - 1}}(u)\bigr].
\end{equation}
Suppose $w_0 \ge K$. Summing \eqref{eq:ov-pivotal} over $w_0 < j \le m < M$ and using the geometric descent, we get
\[
\begin{split}
\Pp(H \le M, \ \max_{v \in e_H}\deg_\Gamma(v) > D_n)
\le \frac83\,4^{-(D_n + 1 - w_0)}\\
{} + \frac{16\Lambda}{3(w_0 - K + 2)}\left(\frac n{n - 1}\right)^2
\sum_{m = 0}^{M - 1}\E[\ind\{\deg_{G_m}(u) \ge w_0\}\beta_{G_m}(u)].
\end{split}
\]
It therefore suffices to bound the sum
\begin{equation}\label{eq:ov-occupation}
\sum_{m = 0}^{M - 1}\E[\ind\{\deg_{G_m}(u) \ge w_0\}\beta_{G_m}(u)].
\end{equation}

The main difficulty is that $\beta_G(u)$ can be of order one for a single colorable graph. For the example of \cref{rem:high-killing}, take $q = 3$, $n \ge 7$, and $n \equiv 1\pmod3$. Let $G$ consist of a triangle, an edge from $u$ to one vertex of that triangle, and, for each triangle vertex, $(n - 4)/3$ additional vertices joined to the other two triangle vertices. Every additional vertex receives the color of the triangle vertex to which it is not joined. The vertex $u$ can take two colors and $C_G(u) = \{u\}$. Here
\[
\beta_G(u) = \frac{2(n - 1)^2}{9n^2}\longrightarrow\frac29.
\]
Adding occurrences from $u$ to vertices forced to have its neighbor's color can increase its degree without changing this relation. Heuristically, this obstructs a useful uniform bound on $\beta_G(u)$ based only on a large degree. For $0 \le m < M$, the elementary degree estimate gives
\[
\Pp(\deg_{G_m}(u) \ge w_0) \le \left(\frac{2e\Lambda}{w_0}\right)^{w_0}.
\]
Bounding $\beta_{G_m}(u)$ by one at each time and summing would give only an upper bound of order $n(2e\Lambda/w_0)^{w_0}$, which does not tend to zero. We instead control the total time spent in such states through growth of the frozen class. In the example, the fraction of frozen pairs tends to one third, so the expected lifetime stays bounded.

For a colorable $G$ and a pair $f = \{a, b\}$, we define its \emph{credited set} $\mathscr A_G(f)$ as follows. If $a, b \in W$, we set $\mathscr A_G(f) = R(a) \cap R(b)$. If exactly one endpoint lies in $W$, we set $\mathscr A_G(f)$ equal to the section of that endpoint. If both endpoints lie in $C_G(u)$, we set $\mathscr A_G(f) = \emptyset$. This definition includes pairs for which $G + f$ is not colorable. We let $\dot \cup$ denote a union of disjoint sets. When $G + f$ is colorable, we apply \cref{lem:high-absorb} with this $G$, the fixed root $u$, and this pair $f$ to get
\[
C_G(u)\,\dot \cup \,\mathscr A_G(f) \subseteq C_{G + f}(u), \qquad
|C_{G + f}(u)| \ge |C_G(u)| + |\mathscr A_G(f)|,
\]
For example, if $a, b \in W$ and $y \in R(a) \cap R(b)$, symmetry gives $a, b \in R(y)$. By \eqref{eq:ov-section}, adding $\{u, y\}$ puts $a, b$ into the class of $u$. The graph $G + \{u, y\} + \{a, b\}$ is then not colorable. Every coloring of $G + \{a, b\}$ must give $y$ the color of $u$.

We now take $f$ uniformly among pairs of distinct vertices of $[n]$, and let $\E_f$ denote expectation over this pair. The main combinatorial estimate is
\begin{equation}\label{eq:ov-onestep}
\beta_G(u) \le \frac{2}{\log 2} \, \E_f \log\Bigl(1 + \frac{|\mathscr A_G(f)|}{|C_G(u)|}\Bigr),
\end{equation}
which bounds the density by the expected credited logarithmic increment. The increment is bounded by the actual growth of the logarithm of the class size when the added pair preserves colorability, and remains defined when it destroys colorability.
To prove this estimate, we use the following inequality from \cref{lem:high-comb}, with the current graph $G$ and root $u$:
\[
\begin{aligned}
|R_G(u)| &\le
2\sum_{(a, b) \in W \times W}\min\left(\frac{|R(a) \cap R(b)|}{|C_G(u)|}, 1\right)\\
&\quad + 2(|C_G(u)| - 1)\sum_{a \in W}\min\left(\frac{|R(a)|}{|C_G(u)|}, 1\right).
\end{aligned}
\]
Its proof uses symmetry to count relation pairs incident to a section of size at least $|C_G(u)|$ through the first sum; pairs for which both sections are smaller are bounded by the second sum. Counting ordered pairs of distinct vertices in the definition of $\mathscr A_G(f)$ then gives
\[
\E_f\min\left(\frac{|\mathscr A_G(f)|}{|C_G(u)|}, 1\right)
\ge \frac{|R_G(u)|}{2n(n - 1)} \ge \frac{\beta_G(u)}2.
\]
Here pairs with one endpoint in $C_G(u)$ supply the second contribution and compensate for the diagonal terms in $W \times W$, which are not possible added edges. Applying $\log(1 + z) \ge (\log 2)\min(z, 1)$ for $z \ge 0$, with $z = |\mathscr A_G(f)|/|C_G(u)|$, proves \eqref{eq:ov-onestep}.

We define $\tau = \min(H, M)$. For integers $0 \le m < H$, we define the \emph{potential} $\Phi_m = \log|C_{G_m}(u)|$ and the \emph{credited logarithmic increment} $\Psi_m = \log(1 + |\mathscr A_{G_m}(e_{m + 1})|/|C_{G_m}(u)|)$. We set $\Phi_m = \Psi_m = 0$ for $m \ge H$. The potential takes values in $[0, \log n]$. By absorption, we have
\[
\Phi_{m + 1} - \Phi_m \ge \Psi_m\qquad\text{when }m + 1 < H.
\]
At the last index before $\tau$, disjointness inside $[n]$ gives
\[
\Psi_{\tau - 1} \le \log n - \Phi_{\tau - 1}.
\]
The pair $e_\tau$ is the final edge if $\tau = H$ and the edge at the cap if $\tau = M < H$. Let $\tau_0$ be a stopping time of $(\cF_m)_{m \ge 0}$ with values in $\{0, 1, \dots\} \cup \{\infty\}$. By telescoping, we have
\[
\sum_{m : \, \tau_0 \le m < \tau} \Psi_m \le (\log n) \ind\{\tau_0 < \tau\}.
\]
For $0 \le m < M$, we apply \eqref{eq:ov-onestep} conditionally on $\cF_m$ with $G = G_m$ and $f = e_{m + 1}$ on the event $m < H$. The fresh pair is uniform and independent of $\cF_m$. Multiplying by the $\cF_m$-measurable indicator of $\{\tau_0 \le m < \tau\}$, summing, and taking expectations gives
\begin{equation}\label{eq:ov-potential}
\E \sum_{m : \, \tau_0 \le m < \tau} \beta_{G_m}(u) \le \frac{2}{\log 2} \, (\log n) \, \Pp(\tau_0 < \tau).
\end{equation}
This estimate controls the total occupation of the process. The final edge must be credited. In the example above, pairs $f$ for which $G + f$ is colorable contribute only $O((\log n)/n)$ to \eqref{eq:ov-onestep}, although $\beta_G(u) \to 2/9$; see \cref{rem:high-killing}.

We now take $\tau_0 = \min\{m \ge 0:\deg_{G_m}(u) \ge w_0\}$, with value $\infty$ if the set is empty. Since degrees are nondecreasing and $\beta_{G_m}(u) = 0$ after $H$, the left side of \eqref{eq:ov-potential} is \eqref{eq:ov-occupation}. For $w_0 \ge K$, applying the binomial tail estimate with number of trials $M - 1$, success probability $2/n$, and threshold $w_0$ gives
\[
\Pp(\tau_0 < \tau) \le \Pp(\Bin(M - 1, 2/n) \ge w_0)
\le \left(\frac{2e\Lambda}{w_0}\right)^{w_0}.
\]
Inserting this bound into \eqref{eq:ov-potential} gives the estimate of \cref{cor:high-degree} with $j = w_0$. This argument uses no independence between the degree and the relation density. Combining it with the descent estimate proves, for $w_0 \ge K$,
\begin{equation}\label{eq:ov-high-final}
\begin{split}
&\Pp\Bigl(H \le M, \ \max_{v \in e_H} \deg_\Gamma(v) > D_n\Bigr) \\
&\qquad \le \frac{8}{3} \, 4^{-(D_n + 1 - w_0)} + \frac{32 \Lambda}{3 \log 2} \Bigl(\frac{n}{n - 1}\Bigr)^2 \frac{\log n}{w_0 - K + 2} \Bigl(\frac{2e\Lambda}{w_0}\Bigr)^{w_0}.
\end{split}
\end{equation}
Since $w_0 \ge (\log n)^{1/4}/2 - 1$, the bound is at most $\eps_n$ for all large $n$, proving \eqref{eq:ov-high}. The argument also holds for $q = 2$ (\cref{rem:high-q2}).