\section{Combining the matching comparisons}\label{sec:certificates}
We now prove that the preceding inequalities cover every labelled
complete graph and imply $\gamma(4)\le\Gnew$. Throughout this
section, $h=|d-q|=2b$ and $m=\min(d,q)$. Numerical bounds on
$\gamma$ include the factor $1/2$ that converts counts divided by
$M^2$ to counts divided by $\binom{2M}{2}$.

\subsection{How the quadratic certificates prove an upper bound}
For a fixed labelled graph, let $C_0,C_1,\ldots$ denote the counts,
divided by $M^2$, of the actual matchings constructed above. For
nonnegative weights $\theta_j$ summing to one,
\[
 \min_j C_j\le\sum_j\theta_j C_j.
\]
We choose the weights so that the coefficients of all uncontrolled
nonnegative missing-edge counts on the right are nonpositive.
Packing inequalities remove the remaining such quantities. The
result is an upper bound $1-\Phi(V)+o(1)$, where $\Phi$ is a
homogeneous quadratic form in the remaining parameters $V$.

Write $\Lambda=x+y+z+w$, which equals one for the normalized
parameters. Suppose the parameter domain gives homogeneous
quadratic inequalities $g_i(V)\ge0$. A certificate consists of
nonnegative rational numbers $\mu_i$ such that
\[
 \Phi(V)-(1-2G)\Lambda^2-\sum_i\mu_i g_i(V)=V^TAV
\]
for a positive semidefinite rational matrix $A$. This identity
implies $\Phi(V)\ge1-2G$ on the domain, hence some matching has
count at most $2G+o(1)$, and the resulting bound is
$\gamma(4)\le G$. Equality constraints may be multiplied by
arbitrary rational numbers. The checkers reconstruct the identity
from the displayed comparisons and the certificate data. They verify
positive definiteness by an exact $LDL^T$ factorization, so no
floating-point eigenvalue calculation is used.

The case division proceeds as follows. The initial and core
comparisons first restrict the parameter domain. The bounds of
Section~\ref{sec:top-capacity} then dispose of small imbalance and
insufficient supply of label-4 vertices. We divide the remaining
cases into $d\ge q$ and $q\ge d$. In the first case the alternatives
in the $AP$ and $CP$ matching comparisons cover the domain; in the
second case the full-target comparison applies. Every restriction
below is established using comparisons valid before that restriction
is imposed.

\subsection{Common parameter restrictions}
The starting certificate and its entry conditions are proved in
Section~\ref{sec:base-certificate}.

The retained conditions are established in two ways. The starting
quadratic residual gives the desired bound whenever any of the
following inequalities fails:
\[
\begin{gathered}
 r,w\ge1/10,\quad z\ge1/5,\quad y\ge187m/1000,\quad
 y\le w,\quad 2y\le z,\\
 r+z\le6w,\quad h\le5m/4,\quad y\le m,\quad z\le3m.
\end{gathered}
\]
These conditions depend only on
$m=\min(d,q)$ and apply in both orientations.
The exact checker verifies that each residual count gap exceeds
$2(23/53-\Gnew)$.

The remaining boundary regions are optimized directly, using the initial
and core inequalities with weights $1-\beta,\beta$, where
$0\le\beta\le1/4$. The initial deficit coefficient $-1$ and core
coefficient at most $3$ are then absorbed. Nonnegative multiples of
\[
 (m-r)(2r-m),\quad \Lambda(m-r),\quad
 \Lambda(r-4m/5)
\]
and the relevant branch and violating-halfspace constraints are
subtracted from the quadratic form. Exact rational positive-definite
residuals give the following \emph{bounds on $\gamma$}, already divided
by two:
\begin{center}\small
\begin{tabular}{lc}
\toprule
Excluded region & Certified bound\\\midrule
$y\ge3z/8$, with $y\le z$ & $0.43324206$\\
$y\ge13m/20$ & $0.43335152$\\
$y\ge z$ & $0.42503599$\\
\bottomrule
\end{tabular}
\end{center}
Their rational weights and multipliers are in
\path{exclusion-certificate.json}. The checker reconstructs each
matrix independently. At this point the retained common conditions
include $y\le3z/8$, $y\le13m/20$, $z\le3m$, and $h\le5m/4$,
but no top-capacity condition or positive lower bound on $h/m$.

Section~\ref{sec:top-capacity} supplies the following additional
exceptions, in this order:
\begin{center}
\begin{tabular}{lrc}
\toprule
Region & Matrices & Bound on $\gamma$\\\midrule
$0\le h\le3m/10$, both orientations and capacity cases &4&$0.433403$\\
$d\ge q\ge2w$, both capacity cases &2&$0.433$\\
$q\ge d\ge2w$, with $h\ge3d/10$ &1&$0.43301$\\
\bottomrule
\end{tabular}
\end{center}
The first uses the raw reservoir with target $\min(r,2w)$ and assumes
no capacity bound. We may then retain $h\ge3m/10$. The next two
exclude $m\ge2w$ in the two orientations, and $r\le m$ also gives
$r\le2w$. This ordering is necessary: the surplus-target capacity
argument uses the positive imbalance established in the first step.
The exact checkers are \path{verify_small_imbalance.py},
\path{verify_ab_boundary.py}, and \path{verify_cd_boundary.py}.
Their domain forms, weights, and coverage checks are reconstructed
from the accompanying rational data. Here $h=2b$ in both orientations;
no condition $h\le r$ is used.

\subsection{\texorpdfstring{Parameter restrictions when $d\ge q$}{Parameter restrictions when d >=  q}}
In this orientation $q=m$, $d=q+h$. The original random-top
comparison and the starting packing inequality give the following
excluded-region bound:
\[
\begin{array}{c|c}
\text{region}&\text{bound on }\gamma\\\hline
r\le7q/8&0.43336741
\end{array}
\]
This bound is verified by \path{verify_ab_good_domains.py};
it uses neither a bound on the missing-edge density within the
retained $C$ set nor either alternative of the $AP$ comparison.
Here and below $Z=z-h_3/r$.

On $r\ge7q/8$, the joint-reservoir inequality gives
\[
 Z\le3r/2\quad\Longrightarrow\quad\gamma\le0.433392.
\]
Five rational seven-variable certificates use the violating form
$zu-rz+3r^2/2\ge0$, where $u=h_3/z$. Their ratio domain is
$h/q\in[3/10,5/4]$, $r/q\in[7/8,1]$, $z/q\in[2/5,3]$;
the last lower endpoint follows from $z\ge1/5$ and $q\le1/2$.
They use the weaker Tutte--Berge resource and impose no good-$P$
lower bound. The checker \path{verify_z_domain.py} verifies
the defect budgets, matrices, and full domain coverage from
\path{z-domain-certificate.json}.

After excluding $r<7q/8$, split according to $c\ge q^2/8$.
In that case the initial and core bounds have the majorants
$B_0-q^2/8$ and $B_0+f_R$. Put
$F=x^2/4+y^2+z^2/2+w^2+b^2$, so $B_0=1-F$.
Take core weight $135283/10^6$ and initial weight its complement.
The corresponding loss form is
\[
 F+\frac{864717}{10^6}\frac{q^2}{8}
 -\frac{135283}{10^6}f_R
 -\frac{69682}{10^6}\Lambda(r-7q/8)
 -\frac{21247}{10^6}(r-7q/8)(q-r).
\]
Here $\Lambda=x+y+z+w$. Subtracting
$(1-2\cdot0.43321)\Lambda^2$ gives a positive-definite rational
six-variable form, checked by \path{verify_high_c.py}.
Thus this case satisfies $\gamma\le0.43321$.
On its complement Lemma~\ref{lem:dense-tutte} applies.

After also excluding $Z<3r/2$, a further two-matrix certificate gives
\[
 d\ge23Z/20\quad\Longrightarrow\quad\gamma\le0.433378.
\]
It combines the initial, core, and joint-reservoir bounds and subtracts a
nonnegative multiple of
\[
 h_3-rz+20rd/23=zu-rz+20rd/23\ge0,
 \qquad u=h_3/z.
\]
The data are in \path{good-domain-new-certificate.json}; its
checker verifies the resource budgets, both ratio boxes, and rational
positive definiteness. It uses the Tutte--Berge inequality
\eqref{eq:TB-core}, without
the additional dense-case estimate.

Both orientations also retain $y\ge187m/1000$. The exact count loss
for its violating halfspace is $23138190/20583940031$, larger than
$2(23/53-\Gnew)$. This localization uses only the starting certificate.
The surviving larger-$AB$ domain is consequently
\[
\begin{gathered}
3/10\le h/q\le5/4,\quad7/8\le r/q\le1,\quad
21/16\le z/q\le3,\quad187/1000\le y/q\le13/20,\\
Z\ge3r/2,\quad d\le23Z/20,\quad c\le q^2/8,
\end{gathered}
\]
together with the common conditions already stated.

\subsection{\texorpdfstring{Three exhaustive alternatives on the larger-$AB$ domain}{Three exhaustive alternatives on the larger-AB domain}}
All three alternatives now use seven coordinates
$V=(x,y,z,w,b,r,u)$, where $u=h_3/z$. In particular, the exact core
loss $(1-y/z)h_3$ is $(z-y)u$, a quadratic form. The ratio coordinates are
\[
(v,\rho,\zeta,\sigma,\upsilon)
=(h/q,r/q,z/q,s/r,y/q)
\]
and their common root box is
\begin{equation}\label{eq:final-root-box}
[3/10,5/4]\times[7/8,1]\times[21/16,3]
\times[0,1]\times[187/1000,13/20].
\end{equation}
Here $s$ is the covered target-$D$ mass in
Section~\ref{sec:swapped-reservoir}. It is not an independent coordinate
of the quadratic form: each box encloses its actual ratio $s/r$.
The $AP$ lemma gives either its saturated comparison or its deficient
comparison. In the latter case use the two $CP$ alternatives with the
single fixed threshold $\alpha=179/1000$. Each of these three cases is
certified on a separate complete partition of \eqref{eq:final-root-box}.

On a box with endpoints $v_i,\rho_i,\zeta_i,\sigma_i,\upsilon_i$,
$i=0,1$, put
\[
 L=\frac{4(1-\rho_0)}{5\rho_0-4},\qquad
 \beta=\alpha_0=\frac1{1+v_0},\qquad K=\frac{q^2-r^2}{2},
\]
\[
 A_T=2+\frac{2-\rho_0}{1+v_0}+L\beta,\quad C_T=1+L,
 \qquad T_0=f_T-\frac{q(q-r)}2-LK.
\]
These coefficients use the globally maximal joint-core resource
\eqref{eq:joint-packing-resource}, dropping its favorable quadratic
term in $a$. This substitution preserves the negative term $-LK$, which is
needed in the quadratic comparison.
For the two-orientation swap comparison choose the tangent parameters
$\epsilon_*=5/64$ and $\eta_{\rm rk}=1/10$ in all three alternatives.
The second parameter uses the cardinality constraint of
Section~\ref{sec:reservoir-rank-coupling}. Put
\[
 g=\tfrac12\operatorname{dist}([\sigma_0,\sigma_1],1/2)^2,\qquad
 A_{\rm box}=[7/4-23\epsilon_*/4+\zeta_1-2\upsilon_0
                         -3\eta_{\rm rk}\rho_0/2]_+.
\]
For saturated $AP$, use the full rectangular swap bound, setting
\[
 D_{\rm box}=\max\{\sigma_0\rho_0,1-\rho_1\},\qquad
 J=\frac{A_{\rm box}}{2D_{\rm box}},\qquad
 E_{\rm box}=A_{\rm box}[1-(1+\sigma_0)\rho_0]_+
\]
when $D_{\rm box}>0$. If $D_{\rm box}=0$, assign the enlarged
comparison zero weight and set $J=E_{\rm box}=0$.
For the two deficient alternatives, use the enlarged comparison only
on boxes satisfying $\sigma_0\rho_0\ge1-\rho_0$, and set
$J=A_{\rm box}/(2\sigma_0\rho_0)$ and $E_{\rm box}=0$ there.
On their other boxes its weight is zero and $J=E_{\rm box}=0$.
These formulas are proved in \eqref{eq:partial-swap-envelope} and
include boxes where only part of the omitted mass can be absorbed.
All conditions are checked exactly, with no division by zero.

After removing the common $B_0=1-F$, the core, joint-reservoir,
profiled initial-reservoir, and enlarged-reservoir columns are
\begin{align*}
 P_R&=f_R-(z-y)u,\\
 P_T&=T_0+zu/2+(\zeta_1/\rho_0)^2u^2/2,\\
 P_D&=T_0-gr^2+(2-\sigma_0)zu-V_{\rm fail},\\
 P_X&=q^2/8-qz+2qy+(\tfrac{23}{8}\epsilon_*^2+E_{\rm box})q^2-(2+J)LK\\
    &\hspace{16mm}+zu/(2\rho_0)+(\zeta_1/\rho_0)^2u^2/2
                      +JV_{\rm fail}\\
    &\hspace{16mm}+\eta_{\rm rk}(\sigma_1-2+\eta_{\rm rk}/2)r^2
                  +\tfrac32\eta_{\rm rk}qr+\eta_{\rm rk}zu.
\end{align*}
The additional terms in $P_X$ follow by applying the tangent
\eqref{eq:rank-tangent-r} and then taking the tangent of
$F(R)+(3\eta_{\rm rk}/2)rR$ at $R=(1-\epsilon_*)q$.
The $s=\sigma r$ term uses the upper endpoint $\sigma_1$.
Here $V_{\rm fail}=\xi+\zeta$ is the unused-charge resource from
Section~\ref{sec:swapped-reservoir}; the letter $\zeta$ in that resource
is unrelated to the ratio coordinate $z/q$.
The enlarged column has coefficients
\[
 A_X=1+\frac1{\rho_0}+\frac{2(1-\rho_0)}{1+v_0}+J
       +(2+J)\left(\frac{\rho_1}{1+v_0}+L\beta\right),
 \qquad C_X=1+(2+J)L
\]
on $a,c$, and coefficient $1+J$ on $j=E_{AC}$.

The remaining auxiliary column depends on the alternative. For
saturated $AP$, put
\[
 \eta=\frac{1+v_1}{\rho_0}-1,\qquad
 A_{AP}=\max\left\{-2+\frac{3(1+v_1)}{\rho_0},
                  \frac{4+6v_1-2\zeta_0}{\rho_0}\right\}.
\]
Then
\[
 P_A=f_R+f_A-(z-y)u+\eta zu,
 \qquad (A_A,C_A,j_A,e_A)=(A_{AP},0,1,3/8).
\]
The last four entries bound its positive coefficients on
$(a,c,j,e_{23})$. For the deficient $AP$ case, define
\[
 K_C=\frac4{(1-\alpha)(5-4/\rho_0)},\qquad \alpha=179/1000.
\]
The large-$CP$ alternative has
\[
\begin{split}
 P_A&=f_R+\alpha r(z+q-3r)-\alpha^2r^2/2
                    +(\alpha-5/8)zu,\\
 (A_A,C_A,j_A,e_A)&=(3\alpha,\alpha,0,3/8).
\end{split}
\]
The small-$CP$ alternative has
\[
\begin{split}
 P_A&=f_R+r(4y-d-r)+\tfrac3{20}r(d-r)+\alpha r^2-K_CK-5zu/8,\\
 (A_A,C_A,j_A,e_A)&=(2+\beta K_C,K_C,0,57/8).
\end{split}
\]
Here the $3/20$ coefficient follows from $d\le23Z/20$, and
$K_C$ follows from the retained-core part of the joint-packing lemma.

Let $p,b_R,b_T,b_A,b_D,b_X$ be the initial and five comparison weights,
nonnegative and summing to one. A nonnegative split-packing multiplier
$\mu$ uses $\alpha_0a+c\ge K$. The exact resource budgets are
\[
\begin{aligned}
p&\ge A_T(b_T+b_D)+A_A b_A+A_Xb_X+\alpha_0\mu,\\
p&\ge C_T(b_T+b_D)+C_A b_A+C_Xb_X+\mu,\\
p&\ge j_A b_A+(1+J)b_X,\\
p&\ge13b_T/2+4b_D+(35/4+7\eta_{\rm rk}/2)b_X,\\
p&\ge e_A b_A,\qquad b_D\ge Jb_X.
\end{aligned}
\]
The last inequality absorbs $V_{\rm fail}$. For saturated $AP$, the
$e_{23}$ inequality follows already from the $j$ inequality. The
remaining $AP$ allowances on $e_{12}$ and $E_{AA}$ are also absorbed;
all other omitted resource coefficients are nonpositive. Thus no
unused-charge resource is treated as a free parameter after combination.

\subsection{Rational matrices and exhaustive coverage}
For clarity we specify the domain multipliers. Let $\mathcal L$
contain the six box faces for $v,\rho,\zeta$, the two faces for
$\upsilon$, and
\[
\begin{gathered}
3z/8-y,\quad13q/20-y,\quad2w-q,\quad6w-r-z,\\
z-(\zeta_0/\rho_1)u-3r/2,\qquad
23[z-(\zeta_0/\rho_1)u]/20-d,\\
x,y,z,w,q,h,d-r,w-y.
\end{gathered}
\]
The good-$P$ forms are valid because
$Z=z-(z/r)u\le z-(\zeta_0/\rho_1)u$; one must not substitute $z-u$
for $Z$. With $\Lambda=x+y+z+w$, subtract the certificate's nonnegative
multiples of $\Lambda L,uL$ for
$L\in\mathcal L$, of $u(r-u)$ and $\Lambda u$, of products of opposite
box faces, and of $q$ times those faces. After adding the split-packing
loss $+\mu K$ and subtracting $(1-2\Gnew)\Lambda^2$, all reconstructed
rational residual matrices have strictly positive $LDL^T$ pivots.

The complete active partitions are
\begin{center}
\begin{tabular}{lrl}
\toprule
Alternative & Matrices & Checker\\\midrule
Saturated $AP$ &1629&\path{verify_swap_cap.py}\\
Deficient $AP$, large $CP$ &36&\path{verify_cp_large.py}\\
Deficient $AP$, small $CP$ &38&\path{verify_cp_small.py}\\
\bottomrule
\end{tabular}
\end{center}
Each checker reads its corresponding JSON certificate, reconstructs
the forms from the displayed scalars, checks every resource budget,
and verifies root-box containment, disjoint interiors, and exact total
five-dimensional volume. The partitions for the two $CP$ alternatives
need not agree: their shared threshold $\alpha$ is fixed globally,
and each partition covers the entire root domain. All three alternatives
therefore give $\gamma\le\Gnew$.

\subsection{\texorpdfstring{The case $q\ge d$}{The case q >=  d}}
Use eight coordinates $(x,y,z,w,b,r,u,t)$ with
$u=h_3/z$, $t=h_3/r$, so $zu=rt$. Set
\[
 d=x/2-b,\quad q=x/2+b,\quad h=2b,\qquad
 K=(d^2-r^2)/2,\quad J_C=q(d-r)/2,
\]
\[
 f_D=d(x+z-3y)-3d^2-dh+5h^2/8.
\]
The 31 boxes in \path{cd-domain-certificate.json} partition
$(h/d,r/d)\in[3/10,5/4]\times[4/5,1]$. On a box put
\[
 P=\frac{10}{9}(53/10+v_1),\qquad
 A_D=P+\frac{v_1}{1+v_1-9/(40\rho_0)},\qquad
 \alpha_0=\frac1{1+v_0},\quad\beta_0=\frac1{9(1+v_0)}.
\]
The initial, core, and full-target weights $p,b_1,c_1$ sum to one and obey
\[
 p\ge c_1,\qquad
 \alpha_0\mu+\nu\le p-A_Dc_1,\qquad
 \mu+\beta_0\nu\le p-Pc_1.
\]
These absorb defects using $K\le\alpha_0a+c$ and
$J_C\le a+\beta_0c$. The resulting loss form is
\[
 F-b_1f_R-c_1f_D+\mu K+\nu J_C
 +(b_1+c_1)(z-y)u-2c_1ht.
\]
The valid linear forms are the four ratio-box faces and
\[
\begin{gathered}
3z/8-y,\quad13d/20-y,\quad3d-z,\quad2w-d,\quad6w-r-z,\\
w-y,\quad y-187d/1000,\quad r-u,\quad z-t,
\quad u,t,x,y,z,w,d,h.
\end{gathered}
\]
Subtract nonnegative multiples of $\Lambda,u,t$ times every listed form,
of opposite box-face products, and of $d$ times the box faces.
Add the certificate's unrestricted multiple of $zu-rt=0$.
In particular, the terms $\Lambda(r-u)$ and $\Lambda(z-t)$ use
the bound $h_3\le rz$, expressed as the linear inequalities
$u\le r$ and $t\le z$.
The exact checker reconstructs the matrices and all budgets and
coverage tests. After subtracting $(1-2\Gnew)\Lambda^2$, all
rational $LDL^T$ pivots are positive. Thus this orientation gives
$\gamma\le\Gnew$ without any of the larger-$AB$ assumptions.

Taking the maximum over both orientations and all exceptional cases
proves
\[
 \boxed{\gamma(4)\le\Gfrac=\Gnew.}
\]