\section{\texorpdfstring{An explicit upper bound for every $\ell\ge5$}{An explicit upper bound for every ell >= 5}}
\label{sec:general-shortened}
We continue with the notation and deficit decomposition of
Section~\ref{sec:general-path-packing}, and put $y=x_1$. Rather than
selecting paths one at a time, we now choose equally many red pairs
from several layers and rematch their endpoints simultaneously.
Choosing fewer than all $p=k/2$ layers permits larger errors in the
layer sizes and in the number of missing blue edges. The resulting
criterion yields an explicit improvement for each $\ell\ge5$,
including the values for which the asymptotic path estimate is weak.

\subsection{Selecting layers with few missing edges}
Fix an integer $j$ with $k/4<j\le p$, and put $n=p-j+1$.
The missing template degree of a vertex is the number of its permitted
blue neighbors in the template that are not actual blue neighbors.
Delete an original red pair if one of its endpoints has missing
template degree greater than $hM$, where $h=\theta/S$ and $\theta>0$.
At most $2EM/h+o(M)$ pairs are deleted. Among the surviving layers,
the $j$th largest mass is at least
\begin{equation}\label{eq:general-quantile}
 \frac{2x}{k}
 -\sqrt{\frac{2(j-1)}{pn}R}-\frac{2E}{nh}-o_\ell(1).
\end{equation}
Indeed for any $n$ original layers, the sum of their masses is at least
\[
 \frac{nx}{p}-\sqrt{2R\,\frac{n(p-n)}p}.
\]
This is Cauchy--Schwarz applied to the centered indicator of those
layers and the vector $(a_i-x/p)_i$. Apply it to the $n$ smallest
surviving layers and subtract the total deletion allowance.

The mass constraint improves the $x$ part of $Q$ to
\[
 |2x/k-2/S|\le
 2\sqrt{\frac{S-k}{kS}Q}.
\]
Consequently, with
\[
 \chi=\frac{4(S-k)}{kS}+\frac{2(j-1)}{pn}
       =\frac2n-\frac4S,\qquad
 B_c=\frac{2S}{n\theta},
\]
the $j$th largest surviving mass is at least
\[
 \frac2S-\sqrt{\chi(Q+R)}-B_cE-o_\ell(1).
\]
For $D\le\delta$, the joint budget $Q+R+E\le D+o(1)$ and a
completed square give the uniform lower bound
\begin{equation}\label{eq:general-clean-radius}
 r_0=\frac2S-\frac{\chi}{4B_c}-B_c\delta.
\end{equation}
Explicitly,
$\sqrt{\chi(\delta-E)}+B_cE
\le B_c\delta+\chi/(4B_c)$.
Choose the same even number $rM$ of surviving red pairs from each
of these $j$ layers, with $r=r_0-o(1)$. If
\begin{equation}\label{eq:general-clean-room}
 r_0>2\theta/S,
\end{equation}
every selected endpoint has fewer than $rM/2-O(1)$ missing template
neighbors. The selected layers inherit their original order.

\subsection{Rematching the selected vertices}
Number the selected layers $1,\ldots,j$ in their inherited order.
They support an alternating path with layer sequence
\[
 1,2,\ldots,j,j,j-1,\ldots,t
\]
and $2j-t+1$ red edges, with any prescribed distinct endpoints in
$R_1$ and $R_t$. To construct it, traverse the red pairs from layer
1 up to layer $j$, use a left--left blue edge between two pairs of
layer $j$, and return through the layers down to $t$. At the join
between the two traversals, an intermediate pair must satisfy at
most two prescribed blue adjacencies; all other choices require at
most one. The missing-degree bound excludes at most
$2hM+O_\ell(1)<rM$ choices, including pairs already used. Thus all
vertices can be chosen distinctly. Every selected $R_1$--$R_t$ pair
must consequently have label $\ell$ when
$2j-t+1>k/2$. In particular, $R_1$ is a label-$\ell$ clique, and
its vertices have exact outward label $\ell$: use a path with $2j$
red edges and replace its closing edge by an edge to an originally
uncovered vertex. A smaller label would decrease original primary
weight from $2j>k/2$ to at most $k/2$.

Make blue perfect matchings between $L_i$ and $R_{i+1}$, a blue
perfect matching inside $L_j$, and any perfect matching inside $R_1$.
The bipartite graphs in the first step have minimum degree greater
than half the part size, so Hall's theorem gives perfect matchings.
The graph on $L_j$ also has minimum degree at least half its even
order and hence has a perfect matching: otherwise two uncovered
vertices of a maximum matching would admit an augmenting path of
three edges. Only $R_1$ is promoted to matching label $\ell$; all
other selected vertices are demoted to matching label 1. The label
restriction to originally uncovered vertices proves that no outward
critical edge is created.

We also have a conditional cross half bound. Let $uv$ be an original
matching edge outside the selected layers, of label $t<\ell$.
If
\[
 2j+2^{t-2}>k\qquad(t\ge2),
\]
two complementary critical contacts from a new $R_1R_1$ pair to
$uv$ are impossible. Replace the $2j$ red edges of an alternating
path joining the $R_1$ endpoints and the old edge $uv$ by the path's
blue edges and these two contacts. The original primary cost is
strictly greater than $k$; the new cost is at most $k$.
Thus the new critical density to $X_t$ is at most $rx_t$ under
this condition and at most $2rx_t$ otherwise. This argument uses
the original matching; it does not assume primary minimality of
the new comparison matching.

Set
\[
 \eta=\begin{cases}1,&j=p,\\2,&j<p,\end{cases}\qquad
 \tau=2j-p,
\]
and for $3\le t<\ell$ set $\alpha_t=1$ if
$2^{t-2}>k-2j$, and $\alpha_t=2$ otherwise. The $X_1$ comparison is
sharper than a trivial bound: original cross half bounds show that
the selected pairs had at least $2jry-e_{12}$ critical contacts to
$X_1$, while the new matching has at most $2ry$.

The selected template originally has
$(j^2-j/2)r^2+O_\ell(1/M)$ blue density, with at most $E$ missing.
The critical count among selected vertices is at most
$(2j-\tau)r^2$: a critical edge must touch $R_1$, and all its edges
to $R_1,\ldots,R_\tau$ have label $\ell$. There are at most $jr^2$
possible critical pairs to the left sides and $(j-\tau)r^2$ to the
remaining right sides. Contacts to omitted
$X_2$ cost at most $\eta r(x-jr)$; contacts to $X_\ell$ cannot
change. Summing these statements gives
\begin{equation}\label{eq:general-short-ledger}
 C_j-C_0\le E+e_{12}+r\Lambda-Ar^2+o_\ell(1),
\end{equation}
where
\[
 A=j^2+(\eta-5/2)j+\tau,\qquad
 \Lambda=\eta x-2(j-1)y+\sum_{t=3}^{\ell-1}\alpha_tx_t.
\]
Write $\lambda_t$ for these coefficients of $x_t$, including
$\lambda_\ell=0$, and put
\[
 \Lambda_0=\frac1S\sum_tc_t\lambda_t,\qquad
 V=\sum_tc_t\lambda_t^2-
       \frac{(\sum_tc_t\lambda_t)^2}{S}.
\]
Weighted Cauchy--Schwarz on the mass hyperplane gives
$\Lambda\le\Lambda_0+\sqrt{VQ}\le\Lambda_0+\sqrt{V\delta}$.
Because $E+e_{12}\le D+o(1)$, these two terms are already included
in the deficit of the initial matching.

\begin{theorem}\label{thm:general-clean-criterion}
Let $\ell\ge5$. Choose $j,\theta,\delta$ as above and define $r_0$
by \eqref{eq:general-clean-radius}. If
\[
 r_0>2\theta/S,\qquad
 r_0\bigl(Ar_0-\Lambda_0-\sqrt{V\delta}\bigr)>\delta,
\]
then
\[
 \gamma(\ell)\le\frac12-\frac1{2S}-\frac\delta2.
\]
Nonstrict limiting choices are valid by approximation whenever the
inequalities hold for a sequence of positive smaller $\delta$.
\end{theorem}
\begin{proof}
If $D\ge\delta-o(1)$, the original matching suffices. Otherwise
construct the shortened layered matching. Equations
\eqref{eq:general-deficit} and \eqref{eq:general-short-ledger} give
$C_j\le1-1/S+r\Lambda-Ar^2+o(1)$. The hypotheses and
$r=r_0-o(1)$ give the claim. All comparisons concern actual finite
matchings and the errors are uniform in $N$.
\end{proof}

\subsection{An explicit bound for every finite number of labels}
\begin{corollary}\label{cor:general-uniform}
For every $\ell\ge5$,
\[
 \boxed{\gamma(\ell)\le\frac12-
 \frac1{3\cdot2^{\ell-1}-4\ell+8}
 -\frac1{162\cdot2^\ell}.}
\]
\end{corollary}
\begin{proof}
Take $j=3k/8+1$ and $\delta=1/(324k)$. For a convenient simple
uniform calculation, replace the coefficient $4(S-k)/(kS)$ in
the layer selection estimate by $4/k$; the total square-root coefficient
is then $\chi=16/k$. Use
\[
 \theta=\begin{cases}1/2,&k=8,\\2/3,&k=16,\\4/9,&k\ge32.
 \end{cases}
\]
The resulting guaranteed layer masses are
\[
 r_0=11/144\quad(k=8),\qquad
 r_0=37/1080\quad(k=16),\qquad
 r_0=\frac{17k^2-S^2}{9Sk^2}\quad(k\ge32).
\]
They strictly exceed $2\theta/S$. In the last case their difference
is $(9k^2-S^2)/(9Sk^2)>0$, since $S<3k$.

For $k=8$, use $A=14$, $\Lambda_0=5/9$, and the conservative
variance upper bound $V=52$. For $k\ge16$, suitable upper bounds are
\[
 A=\frac{9k^2}{64}+\frac{13k}{16}+\frac52,\qquad
 \Lambda_0=2-\frac{3k/4+12}{S},\qquad
 V=\frac{9k^2}{16}+4S-32.
\]
Here the variance bound drops the nonnegative subtracted term in
the formula for $V$. To verify the three smallest cases directly,
put $Z=Ar_0-\Lambda_0-\delta/r_0$. The following rational bounds
give $Z>0$ and $Z^2>V\delta$, which are equivalent to the second
inequality in Theorem~\ref{thm:general-clean-criterion}:
\[
\begin{array}{c|c|c|c}
k&r_0&\text{lower bound for }Z&\text{upper bound for }V\delta\\\hline
8&11/144&1/2&1/40\\
16&37/1080&1/3&1/16\\
32&2503/198144&1/2&1/9
\end{array}
\]
All inequalities in the last two columns are strict. They can be
checked by substitution and are also verified in
\path{general-certificate/verify_general.py}.

For $k\ge64$, use $r_0\ge8/(27k)$, $\Lambda_0\le2$, and
\[
 \sqrt{V\delta}\le\sqrt{k/576+1/27}\le k/144.
\]
The last inequality is equivalent to
$k^2-36k-768\ge0$, valid for $k\ge64$. Consequently
\[
 Ar_0-\Lambda_0-\sqrt{V\delta}
 \ge\frac{5k}{144}-\frac{95}{54}\ge\frac{25}{54}.
\]
Since $2\delta/r_0\le1/48<25/54$, the count criterion holds
even with $2\delta$ on its right side. This proves the corollary.
\end{proof}

For small fixed $\ell$ the full criterion is stronger than this
simple corollary. Rational choices of $(j,\theta,\delta)$ obtained
by optimizing the criterion are saved in
\path{general-certificate/cleanup-certificates.json}; their verification requires no
numerical solver and no floating-point computation.