\section{Enlarging the retained sets by re-pairing}
\label{sec:swapped-reservoir}
We work in the case $d\ge q$. The purpose of this section is to
enlarge the sets of $C$ and $D$ vertices available for the reservoir
matching. The enlargement must preserve the label restrictions that
make changes of matching safe at uncovered vertices.

Index the original $CD$ matching edges as $C_iD_i$. An index is
\emph{retained} if its pair belongs to the neutral core, and
\emph{omitted} otherwise. For a retained index $i$, write $A_i$ for
the vertex joined to $D_i$ by the core's blue $AD$ matching. The
retained and omitted index sets have masses $r$ and
$\delta=q-r$, respectively. Put $H=h_3$, and define
\[
 B_0=B-b^2,\qquad
 F(R)=4qR-\frac{23}{8}R^2-Rz+2Ry-q^2.
\]
Here $b=|d-q|/2$ is the imbalance parameter; $b_3$ below denotes
the mass of exceptional label-3 pairs. The comparisons in this
section are conditional on
\begin{equation}\label{eq:swap-domains}
 r\ge7q/8,\quad q\le2w,\quad z\le3q,\quad r+z\le6w,
 \quad Z=z-H/r\ge3r/2.
\end{equation}
Section~\ref{sec:certificates} proves that the complementary cases
already satisfy the asserted upper bound, using comparisons that do
not assume these conditions. All statements here concern finite
matchings. Harmless parity adjustments and the bounded-degree discarded blue edges cost
$O(M)$, with constants uniform in $N\ge2M$.

Let $C_{\rm ret}$ and $C_{\rm out}$ denote the retained and omitted
$C$ sets. Write
\[
 U=\operatorname{blue}(C_{\rm ret},C_{\rm out}),
\]
where $\operatorname{blue}(U_1,U_2)$ denotes the number of blue edges
between the indicated disjoint sets, divided by $M^2$. Joint
maximality of the core gives
\begin{equation}\label{eq:swap-U}
 U\le\frac rd a+L(c-K+\beta a)+o(1),\qquad
 L=\frac{4(q-r)}{5r-4q},\quad K=\frac{q^2-r^2}{2},\quad
 \beta=\frac qd.
\end{equation}
This follows from Lemma~\ref{lem:joint-packing-resource} by dropping
its favorable $-a^2/(2d^2)$ term. The complete bracket is nonnegative.
The following arguments keep $U$ explicit until the final optimization.

\subsection{A comparison with specified unmatched mass}
Choose a maximum label-3 matching from the initial retained $C$ to
the original label-4 vertices $X_4$. Its even target mass $t$ satisfies
\[
 t\ge r-e_{24}/(2w)-o(1).
\]
On the corresponding target $D$ vertices together with all endpoints
of the exceptional old label-3 pairs, start with the exceptional
matching edges and augment to a maximum matching of labels at most
3. Every exceptional endpoint remains covered. Let $s$ be the mass
of target $D$ vertices covered by this low-label matching; its
unmatched set has mass $t-s$ and is contained in $D$. Pair that set
at label 4. Put $\sigma=s/r\in[0,1]$.

The reservoir counts bound possible gains by counting eligible
pairs of vertices. Some of those pairs cannot actually produce a
gain. For a covered target index $i$ and an omitted index $o$,
record the following two failures:
\begin{enumerate}
\item $C_iC_o$ is nonblue but does not have label 2;
\item $C_iC_o$ is nonblue and $D_iD_o$ does not have label 2.
\end{enumerate}
Let $\xi$ be the sum of their counts divided by $M^2$. A pair
satisfying both conditions contributes twice, because it removes
one possible gain from each of two separate edge counts.
Also let
\[
 \zeta=\frac1{M^2}\#\{(i,o):i\in S,\ C_iD_o\ge3\}
       +\frac1{M^2}\#\{(i,o):i\in S,\ D_iC_o\ge3\},
 \qquad V=\xi+\zeta,
\]
where $S$ is the set of covered target-$D$ indices, and an expression
such as $C_iD_o\ge3$ abbreviates $\lambda(C_iD_o)\ge3$. These
failures remove possible direct $CD$ gains: $C_i$ has birth three,
and $D_i$ has birth at most three, while omitted vertices retain
birth two. The corrections $\xi$ and $\zeta$ apply to disjoint types
of edges, namely $CC,DD$ and $CD,DC$, respectively. The discarded
blue $CD$ incidences contribute only $O(M)$.

\begin{lemma}\label{lem:profile-reservoir}
Some actual matching satisfies
\begin{align}
 C_I\le{}&B_0+F(r)-\frac12(s-r/2)^2+(2-\sigma)H-V\notag\\
 &+\left(2+\frac{2\delta}{d}\right)a+c-E_{AA}+U
 +4e_{24}-e_{13}-e_{14}-I_3+o(1).
 \label{eq:profile-reservoir}
\end{align}
\end{lemma}
\begin{proof}
Let $b_3\le H/r+o(1)$ be the exceptional pair mass. The low-label
matching covers $s+2b_3$ vertices. The three-edge augmentation
obstruction therefore bounds the combined internal $DD(3)$ and
$D$--exceptional label-3 gains by $(t-s)(s/2+b_3)+o(1)$.
The remaining outside-target label-3 gains with blue $CC$ mates cost
at most $(t-s)(r-t)+U$. Nonblue-mate gains share the single $DD$
missing-edge allowance, as in the disjoint reservoir argument.

The direct $CD$ gain is at most $2tq-t^2$. The top losses to retained
$C$ and good $P$ are at least $tr-e_{24}$ and
$t(z-b_3)-e_{34}$. The $X_1$ comparison costs at most
$2ty+e_{12}$; good-$P$ failures cost at most $e_{23}$.
After separating the missing-edge terms, the target-dependent
polynomial is
\[
 G(t)=t(2q-r-z+b_3+2y)-t^2
       +(t-s)(r-t+s/2+b_3).
\]
Keeping $s,b_3$ fixed, its derivative is
\[
 G'(t)=2q-z+2b_3+2y-4t+3s/2\ge-2r-z.
\]
Replacing $t$ by $r$ consequently costs at most
$(2r+z)e_{24}/(2w)\le4e_{24}$.
At $t=r$, the last term together with the good-$P$ loss is
\[
 \frac{r^2}{8}-\frac12(s-r/2)^2+(2r-s)b_3.
\]
Use $(2r-s)b_3\le(2-\sigma)H+o(1)$.

The direct $A,B$ allowances are
$2a+j+(t/r)a$. Both positive $CC$ charges exclude pairs entirely
outside the initial retained $C$, whose missing density is at least
$\delta^2/2-a\delta/d-o(1)$. Add the initial matching count and
subtract the two corrections defining $V$. The $e_{12},e_{23},e_{34}$ terms
cancel, the $a$ coefficient is at most $2+2\delta/d$, and the main
polynomial becomes $F(r)$. This proves the claim.
\end{proof}

\subsection{Two ways to re-pair a retained and an omitted pair}
On the covered target indices and omitted indices permit either of the
links
\begin{equation}\label{eq:swap-link}
\begin{array}{c|c|c}
 &\text{required contacts}&\text{replacement label-two pairs}\\\hline
\text{straight}&C_iC_o=D_iD_o=2,\quad A_iC_o=1&C_iC_o,\ D_iD_o\\
\text{crossed}&C_iD_o=D_iC_o=2,\quad A_iD_o=1&C_iD_o,\ D_iC_o.
\end{array}
\end{equation}
A pair lacking a straight link is charged to $\xi$, $U$, or a missing
$AC$ contact. A pair lacking a crossed link is charged to $\zeta$,
a missing $AD$ contact, or a discarded blue $CD$ incidence. A pair
lacking both must be charged in both lists. Thus the density of
missing links in their union is at most
$(V+U+a+j)/2+o(1)$. The rectangular vertex-cover bound gives a
matching of $kM+O(1)$ links with
\begin{equation}\label{eq:swap-coverage}
 k\ge\min(s,\delta)-\frac{V+U+a+j}{2\max(s,\delta)}-o(1).
\end{equation}
If both sides have zero mass, take $k=0$. When $s\ge\delta>0$,
this reduces to $k\ge\delta-(V+U+a+j)/(2s)-o(1)$. The same
inequality also permits enlargement when $s<\delta$.
For each link use one available orientation. The disjoint label-two
replacements preserve the entire formal weight vector, every original
vertex birth, the old critical count, and all cross-class deficits.
For a straight link add $D_o$ to the eligible $C$ pool and $C_o$ to
the eligible $D$ pool; for a crossed link add $C_o$ to the $C$ pool
and $D_o$ to the $D$ pool. Denote the resulting pools by $C^*$ and $D^*$. Both contain their
original retained sets and have mass $R=r+k$. The replacement
label-2 pairs match the two pools.

\begin{lemma}\label{lem:swap-caps}
Every vertex of $D^*$ has exact outward and top label 4, and label 4
to every good $Q$. Every vertex of $C^*$ has outward and top labels
at least 3, and labels at least 3 to every good $Q$.
\end{lemma}
\begin{proof}
The assertions for initially retained vertices were already proved.
For a straight selected pair, the actual core replacement
\[
 A_iD_i(1),C_oD_o(2)\longrightarrow A_iC_o(1),D_iD_o(2)
\]
is primary-neutral and preserves all initial $CC$ and $BB$ links.
It places $C_o$ in an $AD$ role. The usual switches with a $BB(4)$
edge prove its outward, top, and good-$Q$ label-4 caps.

For $D_o$, the link $C_oC_i=2$ proves the outward cap by mate release.
If $D_ou\le2$ for an originally uncovered $u$, replacing
$C_oD_o(2)$ by $D_ou(2)$ would preserve primary weight and leave
$C_o$ uncovered, contradicting the retained $C_i$ cap. A label-1
edge is already a primary improvement.
For the top cap, let $C_iC_j(1)$ be its retained $CC$ link, let
$A_jD_j(1)$ be the corresponding $AD$ link, and pair the old mate
$B_j$ of $A_j$ with another initial $B'$ at label 4. A putative
$D_oT\le2$ permits
\[
 \begin{split}
 &B_jB'(4),C_iC_j(1),A_jD_j(1),C_oD_o(2),TT'(4)\\
 &\qquad\longrightarrow
 D_oT(\le2),C_oC_i(2),C_jD_j(2),A_jB_j(2),B'T'(\le4),
 \end{split}
\]
reducing primary cost from 9 to at most 8. For a good pair $PQ$,
replace $TT'(4)$ by $PQ(3)$ and choose $B'$ with $PB'=3$.
The same switch would reduce cost from 7 to at most 6 if $D_oQ\le2$.
The fixed threshold of four neighbors makes all choices disjoint.
\end{proof}

\paragraph{Explicit caps for a crossed link.}
Assume $C_iD_o=D_iC_o=2$ and $A_iD_o=1$, where
$A_iD_i=1$ belongs to the old neutral core and $A_iB_i=2$ was
an original red pair. The primary-neutral replacement
\[
 A_iD_i(1),C_oD_o(2)\longrightarrow A_iD_o(1),D_iC_o(2)
\]
keeps all old $CC$ and $BB$ core edges. Thus $D_o$ becomes an $AD$
endpoint in an actual primary-minimal matching, and $C_o$ has
remaining birth two.

The following switches prove that $D_o$ has label four to an
originally uncovered vertex $u$, an old top vertex $T$, and every
good $Q$, respectively. Choose the auxiliary $B'$ distinct from
$B_i$; in the last line choose it among the retained label-three
neighbors of $P$:
\[
\begin{aligned}
 B_iB'(4),A_iD_o(1)
   &\longrightarrow A_iB_i(2),D_ou(\le3),\\
 B_iB'(4),A_iD_o(1),TT'(4)
   &\longrightarrow A_iB_i(2),D_oT(\le3),B'T'(\le4),\\
 B_iB'(4),A_iD_o(1),PQ(3)
   &\longrightarrow A_iB_i(2),D_oQ(\le3),PB'(3).
\end{aligned}
\]
Their primary costs decrease from $4,8,6$ to at most $3,7,5$.
The first switch leaves $B'$ uncovered instead of $u$.

For $C_o$, use the original matching and $A_iD_i=1$. A putative
outward or top label at most two gives
\[
\begin{aligned}
 A_iB_i(2),C_iD_i(2),C_oD_o(2)
   &\longrightarrow A_iD_i(1),C_iD_o(2),C_ou(\le2),\\
 A_iB_i(2),C_iD_i(2),C_oD_o(2),TT'(4)
   &\longrightarrow A_iD_i(1),C_iD_o(2),C_oT(\le2),B_iT'(\le4).
\end{aligned}
\]
The costs decrease from $3,7$ to at most $2,6$. For the good-$Q$
cap, let $C_iC_j=1$ be the old core edge and let $A_jD_j=1$ be the
core link at its other endpoint. Choose a core $B'$ with $PB'=3$
and re-pair $B_jB'$ at label four. Then
\[
\begin{split}
 &B_jB'(4),C_iC_j(1),A_jD_j(1),C_oD_o(2),PQ(3)\\
 &\quad\longrightarrow
 C_oQ(\le2),D_oC_i(2),C_jD_j(2),A_jB_j(2),B'P(3)
\end{split}
\]
decreases primary cost from $7$ to at most $6$.
The fixed good-pair threshold supplies disjoint auxiliary choices.
These switches prove all the claimed label restrictions for the
crossed orientation. Each restriction follows from the existence of
the stated edges and the minimality of the initial matching.

An original $B$ vertex whose mate $A_0$ has two blue neighbors among the initial
retained $D$ sees every $D^*$ vertex at label 4, except for $O(M)$
own-slot incidences. For a selected new $D$ endpoint, first make its single
core exchange in the preceding proof, then insert $A_0$ at a different
original $D$ slot. The usual $BB(4),AD(1)$ switch applies. These are
individual witnesses; the inserted rows need not all coexist in one
core. The remaining weak rows have mass at most $a/r+o(1)$.

\subsection{The enlarged reservoir count}
\begin{lemma}\label{lem:extended-reservoir}
For every $R=r+k$ supplied by \eqref{eq:swap-coverage}, there is an
actual matching satisfying
\begin{align}
 C_E\le{}&B_0+F(R)+c-E_{AA}
 +\left(1+\frac Rr+\frac{2\delta}{d}\right)a+j+2U\notag\\
 &+\frac{R}{2r}H+\frac{H^2}{2r^2}
 +\frac{35}{4}e_{24}-e_{13}-e_{14}-I_3+o(1).
 \label{eq:extended-reservoir}
\end{align}
\end{lemma}
\begin{proof}
Uniformly sample $RM$ old top vertices and match $C^*$ to them at
label 3. By Lemma~\ref{lem:swap-caps} and the unchanged original
cross half bounds, the total missing $C^*$--top label-3 density is
at most $e_{24}$. The actual target mass $t'$ therefore satisfies
$\mathbb E(R-t')\le e_{24}/(2w)+o(1)$.
Use the joint low-label matching on its $D^*$ mates and all exceptional
old label-3 endpoints. All exceptional births only decrease; every
promoted vertex has the exact outward cap proved above.

Orient all $CD$ pairs after the swaps as $C_{\rm new},D_{\rm new}$.
Their missing $A$-edge densities obey $a_{\rm new}+j_{\rm new}=a+j$.
The direct gains involving $A,B$ cost at most
$2a_{\rm new}+j_{\rm new}+(t'/r)a$.
Indeed a new $C$--$B$ label-2 edge forces its complementary $AD$
link to be missing; new $D$--$A$ and $C$--$A$ gains require missing
$AD$ and $AC$ links, respectively. The last term is the weak-row
allowance just proved. After subtracting the old $a+j$ this is at
most $(1+R/r)a+j$.

Partition the originally omitted indices into straight-selected
$O_s$, crossed-selected $O_c$, and unselected $O_0$. Only $O_s$
exchanges its old $C,D$ memberships. Let $e_{\rm out}$ count all old
blue pairs inside the omitted $C$ set, and let subscripts indicate
their support. Up to discarded $O(M)$ incidences,
\[
 c_{\rm new}=c+U_{O_s}+e_{\rm out,incident\ O_s}.
\]
Both positive missing-$CC$ charges exclude pairs entirely outside the
expanded $C$ pool, whose density is
$(q-R)^2/2-e_{{\rm out},O_0O_0}+o(1)$. The remaining disjoint $DD$
blue-mate allowance is at most
$U_{O_0}+e_{{\rm out},O_cO_0}+o(1)$. Hence, including the old $-c$,
their sum is bounded by
\[
\begin{aligned}
 c-(q-R)^2+2U_{O_s}+U_{O_0}
 &+2e_{\rm out,incident\ O_s}
 +2e_{{\rm out},O_0O_0}+e_{{\rm out},O_cO_0}\\
 &\le c-(q-R)^2+2U+2e_{\rm out}\\
 &\le c-(q-R)^2+2U+2a\delta/d+o(1).
\end{aligned}
\]
The three outside-edge supports on the first line are disjoint.
This proves that mixing the two orientations introduces no additional
resource charge. In particular, this estimate is valid when links of both
orientations are selected in the same matching.

The direct $CD$ gain is $2t'q-t'^2$. The joint internal-$DD$ and
exceptional-pair allowance is
$(R-t'/2+b_3)^2/2$, in addition to the missing-edge charges just
handled. Random top demotion loses at least $R^2-R\mathbb E(R-t')
-Re_{24}/(2w)$ contacts to $C^*$ and
$Rz-2z\mathbb E(R-t')-Re_{34}/(2w)$ to old $X_3$.
The target polynomial before these losses has derivative at least
$-R/4-b_3/2$. At $t'=R$ its exceptional contribution is
$Rb_3/2+b_3^2/2\le RH/(2r)+H^2/(2r^2)+o(1)$.
The complete $e_{24}$ coefficient is
\[
 \frac{9R/4+2z+b_3/2}{2w}-1\le\frac{35}{4},
\]
using $R\le q\le2w$, $z\le3q$, and $b_3\le z$.
The $e_{34}$ coefficient is $R/(2w)-1\le0$.
The $X_1$ half bound costs $2Ry+e_{12}$, and the good-$P$ failure
allowance is $e_{23}$; both deficits cancel their old terms.
Collecting the main terms gives $F(R)$ and proves the claim.
\end{proof}

\subsection{An optimized tangent envelope}
For $0\le\varepsilon\le1$, concavity of $F$ gives the tangent bound
\[
 F(R)\le F(q)+\frac{23}{8}\varepsilon^2q^2
 +\left[\left(\frac74-\frac{23}4\varepsilon\right)q+z-2y\right](q-R).
\]
It is the tangent at $R=(1-\varepsilon)q$. Replacing the bracket by
its positive part remains valid because $R\le q$.
If $\sigma=s/r\ge1/7$, then $s\ge\delta$, so put
\[
 J_\varepsilon=
 \frac{[(7/4-23\varepsilon/4)q+z-2y]_+}{2\sigma r}.
\]
The doubled denominator records the availability of both orientations.
Substituting \eqref{eq:swap-coverage} in the extended count yields
\begin{align}
 C_E\le{}&B_0+F(q)+\tfrac{23}{8}\varepsilon^2q^2+c-E_{AA}\notag\\
 &+\left(1+\frac qr+\frac{2\delta}{d}+J_\varepsilon\right)a
 +(1+J_\varepsilon)j+(2+J_\varepsilon)U+J_\varepsilon V\notag\\
 &+\frac q{2r}H+\frac{H^2}{2r^2}
 +\frac{35}{4}e_{24}-e_{13}-e_{14}-I_3+o(1).
 \label{eq:extended-envelope}
\end{align}
The comparison \eqref{eq:profile-reservoir} has coefficient $-1$
on $V$. Thus a convex combination eliminates the positive $V$ term
in \eqref{eq:extended-envelope} whenever the weight on
\eqref{eq:profile-reservoir} is at least $J_\varepsilon$ times the
weight on \eqref{eq:extended-envelope}. Equation~\eqref{eq:swap-U}
and the split packing inequality then control the other missing-edge
terms. On parameter intervals where this enlargement is not used,
\eqref{eq:profile-reservoir} remains available with its negative
square term.

The choice $\varepsilon=0$ gives the endpoint tangent. Choosing
$\varepsilon$ closer to the actual fractional enlargement retains
more of the concave polynomial. Every value of $\varepsilon$ gives a valid bound throughout the
stated domain; the choice only changes its strength.

\input{rank-coupling}