\section{The initial matching and its structural properties}\label{sec:foundations}
In the four-label problem, fix a labeling of $K_N$ and an integer
$M\le N/2$. Among all $M$-edge matchings choose $\M_0$ minimizing
lexicographically
\[
 (n_2+2n_3+4n_4,\ n_3+2n_4,\ n_4),
\]
where $n_i$ is the number of its edges of label $i$. This is the
matching order of Cs\'oka and Pongr\'acz~\cite{CP}. Formal weights
\[
 w_1=0,\quad w_2=1,\quad w_3=2+\varepsilon,
 \quad w_4=4+2\varepsilon+\varepsilon^2
\]
give an equivalent notation for this order. We
compare polynomials at their first differing coefficient. Alternatively
one may choose a sufficiently small positive $\varepsilon$ for the
given finite instance. The formal order avoids any need for a uniform
choice of $\varepsilon$ as $M$ grows.

The coefficients of $1,\varepsilon,\varepsilon^2$ are called the
primary, secondary, and tertiary weights, respectively. A replacement
that decreases the first coefficient where they differ contradicts
the choice of $\M_0$.

Let $X_i$ be the endpoints of the initial label-$i$ matching edges.
An \emph{outward} edge joins a covered vertex to an uncovered vertex.
An outward critical edge could replace its incident matching edge and
strictly decrease the weight, so none exists. Between two differently
labeled matching edges, the four cross edges form two complementary
pairs. Both edges of a complementary pair cannot be critical: if
the larger original label is $j$, their labels would both be below
$j$, and $2w_{j-1}<w_j$ shows that the replacement has smaller
formal weight.
Thus each such rectangle has at most two critical edges. Its deficit
from two is nonnegative, even before summing over rectangles. There
are no internal critical edges in $X_1$. There are none in $X_4$
either, since an edge of label at most three and its complementary
edge would replace two label-4 matching edges at smaller primary weight.

\subsection{\texorpdfstring{Decomposing the label-1 graph inside $X_2$}{Decomposing the label-1 graph inside X2}}
Color the original $X_2$ matching red and its label-1 edges blue.
An alternating path or cycle has edges alternating between red and
blue; the paths used here begin and end with a red edge.
There is no alternating cycle. There is also no alternating path with
four blue edges: completing such a path by the edge between its ends
would replace five red edges of primary cost five by four blue edges
and an edge of primary cost at most four.

The following special case of the peeling argument in~\cite{CP}
gives the decomposition we need. We include the proof.

\begin{lemma}\label{lem:two-stage-peeling}
Let a graph consist of a red perfect matching and a disjoint set of
blue edges. Suppose there is no alternating cycle and no alternating
path with four blue edges. Remove every red pair having an endpoint
of blue degree at most three. The remaining graph has no alternating
path with two blue edges, and each of its red pairs has an endpoint
of residual blue degree at most one.
\end{lemma}
\begin{proof}
For a longest red-ended alternating path with $p$ blue edges, each
endpoint has blue degree at most $p$. Indeed, a blue neighbor outside
the path and its red mate would extend the path. Among the $p$ other
red pairs on the path, at most one endpoint of each pair can be a
blue neighbor: the other choice closes an alternating cycle.

Let $G'$ be the remaining graph. If it is empty there is nothing to
prove. Otherwise let $P$ be a longest red-ended
alternating path in $G'$, with endpoints $u,v$ and $p$ blue edges.
We have $p\le3$, while every vertex of $G'$ has blue degree at least
four in the original graph. If $p=3$, $u$ has a blue neighbor in a
deleted pair. Adding that blue edge and its neighbor's red edge
extends $P$ to a path with four blue edges, a contradiction.
If $p=2$, both $u$ and $v$ have at least two blue neighbors among
the deleted vertices. Choose distinct such neighbors $u',v'$.
They cannot be red mates: the two blue edges, the path $P$, and
the red edge $u'v'$ would form an alternating cycle. Thus their red
pairs are distinct and outside $P$. Extending at both ends by the two blue edges and
these red pairs again gives four blue edges. Hence $p\le1$.

Finally, if both ends of a residual red edge had blue degree at
least two, choose distinct blue neighbors of its endpoints. The
two neighbors cannot be red mates, by the alternating-cycle
condition, so adding their red mates gives a red-ended alternating
path with two blue edges. This contradiction proves the last claim.
\end{proof}

Apply the lemma by removing
every red pair having an endpoint of blue degree at most three in the
original blue graph. Call the low-degree endpoints $B$ and their mates
$A$. The remaining graph has no alternating path with two blue edges.
In each remaining red
pair select an endpoint of residual blue degree at most one, call it
$D$, and call its mate $C$. Deleting at most $O(M)$ blue incidences
therefore leaves blue edges only in
\[
 AA,\quad AC,\quad AD,\quad CC.
\]
The $AB$ and $CD$ pairs have masses $d$ and $q$ after division by $M$.
Here $d+q=x=|X_2|/(2M)$. The number of possible blue template pairs is
\[
 \frac{d^2}{2}+2dq+\frac{q^2}{2}
 =\frac{3x^2}{4}-\frac{(d-q)^2}{4}
\]
in units of $M^2$, up to $O(1/M)$. Write
$E_{AA},E_{AC},E_{AD},E_{CC}$ for their missing-blue densities.
We call these four permitted regions the \emph{template}. A missing
blue pair in a region is a vertex pair whose edge has label at least
two. At most a constant times $M$ blue edges have been discarded,
independently of the number of uncovered vertices.

Inside $X_3$, the graph of labels at most two has no alternating
cycle or alternating path with two low-label edges. In the path case,
three old label-3 edges have primary cost six; the two low-label edges
and a closing label-4 edge have primary cost at most six, and in the
tie case secondary cost at most two instead of three. The last
paragraph of the preceding proof shows that each original label-3
pair has an endpoint of degree at most one in the low-label graph.
Discard all edges incident to one such endpoint from each pair; this
removes at most $zM$ edges, where $z=|X_3|/(2M)$. All remaining
low-label edges lie on the other $zM$ endpoints, giving the bound
$z^2M^2/2+O(M)$.

\subsection{Matching facts used below}
We use three classical results with their finite forms. K\H{o}nig's
theorem~\cite{Konig} identifies the maximum matching size with the
minimum vertex-cover size in a bipartite graph. In a bipartite graph
with sides of sizes $m\le D$ and $a$ missing edges, it implies a
matching of size at least $m-a/D$: a cover of size $t$ covers at most
$tD$ edges.

If an $n$-vertex graph has matching number $k$, the
Erd\H{o}s--Gallai bound~\cite{EG} is
\[
 e(G)\le\max\left\{\binom{2k+1}{2},\ kn-\binom{k+1}{2}\right\}.
\]
In particular $e(G)\le kn+O(n)$. Finally the Tutte--Berge formula
\cite{Tutte,Berge,Schrijver} gives
\[
 2\nu(G)=\min_{S\subseteq V(G)}
       \bigl(|V(G)|+|S|-o(G-S)\bigr),
\]
where $o(G-S)$ counts odd components. We explicitly derive the
additional stability estimate needed here, rather than assume a
stability theorem from the literature.

We will also use the following dense-graph consequence of the
Erd\H{o}s--Gallai inequality. Suppose a graph has $tM$ vertices and
at most $cM^2+O(M)$ missing edges, where $c\le9t^2/50$. If a maximum
matching covers $RM$ vertices, then
\begin{equation}\label{eq:dense-matching-corollary}
 R^2\ge t^2-2c-o(1),\qquad R\ge4t/5-o(1).
\end{equation}
Indeed the two asymptotic branches of the edge bound are $R^2/2$
and $Rt/2-R^2/8$. For $R\le4t/5$, both are at most $8t^2/25$,
whereas the edge density is at least $t^2/2-c\ge8t^2/25$.
For $R\ge4t/5$ the first branch is the larger one, which gives
\eqref{eq:dense-matching-corollary}. Equality at the branch boundary
and the $O(M)$ terms are accommodated by the stated $o(1)$ errors.

We repeatedly augment a matching while preserving all vertices it
already covers. This is possible because an augmenting path changes
only the matching status of its two previously uncovered endpoints;
the internal vertices stay covered~\cite{Berge}. A related elementary
count will be useful. If $U$ is the unmatched set of a maximum matching,
then the endpoints of any matched edge have at most $|U|+1$ neighbors
in $U$ in total. Otherwise there are two distinct unmatched neighbors,
one at each end, giving an augmenting path of three edges. The possible
extra one contributes only $O(M)$ in the applications below.