\section{A bound uniform in the path length}\label{app:uniform}

We prove Theorem~\ref{thm:uniform} using only positions
\(1,2,L-2,L-1\), so the construction uses four endpoint counts for
every \(L\ge5\). A four-coordinate Sidon labeling provides the counts;
we balance and realize them as landmark selections, then recover
each edge from its histogram.

\subsection{Four-coordinate labels}

The four counts must identify endpoint pairs at central edges and
still permit recovery away from the center. We obtain labels with
both properties by writing a finite-field parabola in four
coordinates, then scale and balance them so that binary matrices
realize the counts. Fix integers \(n\ge222\) and \(L\ge5\), and let \(q\) be the least prime strictly larger than \(\lceil\sqrt n\rceil\). Choose a nonsquare \(\nu\in\F_q\) and \(n\) distinct pairs
\[
(u_i,v_i)\in\F_q\times\F_q^\times.
\]
Index these pairs by \(0\le i<n\).
There are enough pairs because \(q(q-1)\ge n\). With representatives in \(\{0,\ldots,q-1\}\), put
\begin{equation}\label{uniform:eq:code}
c_i=(u_i,v_i,\ u_i^2+\nu v_i^2\bmod q,\ 2u_iv_i\bmod q).
\end{equation}
The first two coordinates identify \(i\), and \(v_i\ne0\).

\begin{lemma}\label{uniform:lem:sidon}
The vectors \(c_i\) have distinct unordered pair sums in \(\Z^4\), including pairs with repetition.
\end{lemma}
\begin{proof}
In \(\F_{q^2}=\F_q(\sqrt\nu)\), put \(x_i=u_i+v_i\sqrt\nu\). An equality of integer vector sums implies
\[
x_i+x_j=x_k+x_\ell,\qquad x_i^2+x_j^2=x_k^2+x_\ell^2.
\]
Since \(q\) is odd, the products also agree. Both pairs are the roots of the same monic quadratic. The pairs of indices therefore agree as multisets. This is the finite-field parabola construction of~\cite{cilleruelo,ruiz}, in coordinates.
\end{proof}

The four coordinates will determine counts at positions
\(1,2,L-2,L-1\), in that order. Their margins must have matching
totals. For \(t\in\{1,2,3,4\}\), define
\[
\mu_t=\left\lfloor\frac{3\sum_i c_{i,t}}n\right\rfloor,\qquad
R_t=3\sum_i c_{i,t}-n\mu_t\in\{0,\ldots,n-1\},
\]
and set \(m=3q-2\), \(T=2m=6q-4\).
The number \(T\) is the common base of each target margin.
Start with \(T+3c_{i,t}-\mu_t\). In coordinate \(3\), add
\(\sigma_3=\sgn(R_2-R_3)\) to exactly \(|R_2-R_3|\) entries. In coordinate \(4\), add
\(\sigma_4=\sgn(R_1-R_4)\) to exactly \(|R_1-R_4|\) entries. The chosen entries may, for example, be the first ones in the indexing of the vertices. Write these corrections as \(\varepsilon_{i,t}\), with \(\varepsilon_{i,1}=\varepsilon_{i,2}=0\), and define
\begin{equation}\label{uniform:eq:degrees}
D_{i,t}=T+3c_{i,t}-\mu_t+\varepsilon_{i,t},\qquad D_i=(D_{i,1},\ldots,D_{i,4}).
\end{equation}
Then
\begin{equation}\label{uniform:eq:balance}
\sum_iD_{i,1}=\sum_iD_{i,4}=nT+R_1,\quad
\sum_iD_{i,2}=\sum_iD_{i,3}=nT+R_2,\quad
m\le D_{i,t}\le3m.
\end{equation}
The last bounds use \(0\le\mu_t\le3(q-1)\) and \(|\varepsilon_{i,t}|\le1\).

\begin{lemma}\label{uniform:lem:robust}
The vectors \(D_i\) retain distinct unordered pair sums. In each of their first two coordinates, the possible values differ by multiples of three.
\end{lemma}
\begin{proof}
In each corrected coordinate all corrections belong to \(\{0,\sigma_t\}\) for one fixed sign \(\sigma_t\). The difference between two sums of two corrections has absolute value at most two. Hence an equality \(D_i+D_j=D_k+D_\ell\) forces
\(c_i+c_j=c_k+c_\ell\) coordinatewise: the other part of the difference is a multiple of three. Apply Lemma~\ref{uniform:lem:sidon}. The first two coordinates have no corrections, which proves the second assertion.
\end{proof}

Apply Lemma~\ref{lem:margins} to \((D_{\cdot,1},D_{\cdot,4})\) and
\((D_{\cdot,2},D_{\cdot,3})\). By~\eqref{uniform:eq:balance}, their totals are at least \(nT\), and their maximum is at most \(\Delta=3m\). The sufficient inequality becomes
\begin{equation}\label{uniform:eq:threshold}
\Delta(\Delta+1)\le nT
\quad\Longleftrightarrow\quad
2n\ge27q-15.
\end{equation}
It also implies \(\Delta<n\): \(n\ge(3/2)(\Delta+1)>\Delta\).

For \(n\ge1024\), Bertrand's postulate gives \(q<2\lceil\sqrt n\rceil<2\sqrt n+2\). The inequality \(2n\ge54\sqrt n+39\) holds at \(n=1024\) and its left side minus its right side is increasing thereafter. This proves~\eqref{uniform:eq:threshold}. Table~\ref{uniform:tab:primes} covers the remaining interval; the left endpoint of each interval suffices.

\begin{table}[htbp]
\centering\footnotesize
\caption{Prime intervals establishing~\eqref{uniform:eq:threshold} for \(222\le n<1024\). For each interval, \(q\) is the least prime strictly exceeding \(\lceil\sqrt n\rceil\).}\label{uniform:tab:primes}
\begin{tabular}{@{}rcc@{\hspace{1cm}}rcc@{}}
\toprule
Range of \(n\) & \(q\) & \(27q-15\) & Range of \(n\) & \(q\) & \(27q-15\)\\
\midrule
\(222\text{--}256\) & 17 & 444 & \(485\text{--}784\) & 29 & 768\\
\(257\text{--}324\) & 19 & 498 & \(785\text{--}900\) & 31 & 822\\
\(325\text{--}484\) & 23 & 606 & \(901\text{--}1023\) & 37 & 984\\
\bottomrule
\end{tabular}
\end{table}

Let \(M^{(1)},M^{(2)}\) be any two matrices realizing these pairs of margins.
For every \(i<j\), select vertices according to
\begin{equation}\label{uniform:eq:marks}
\eta_{ij}(1)=M^{(1)}_{ij},\quad
\eta_{ij}(2)=M^{(2)}_{ij},\quad
\eta_{ij}(L-2)=M^{(2)}_{ji},\quad
\eta_{ij}(L-1)=M^{(1)}_{ji}.
\end{equation}
Let \(W\) consist precisely of these selected vertices. The four positions are distinct for \(L\ge5\).
Their degree profile is
\[
(D_i(1),D_i(2),D_i(L-2),D_i(L-1))=D_i.
\]
Writing \(T_1=\sum_iD_i(1)\), \(T_2=\sum_iD_i(2)\), we obtain
\begin{equation}\label{uniform:eq:size}
|W|=T_1+T_2=2nT+R_1+R_2<(12q-6)n<24n^{3/2}+18n.
\end{equation}
Thus the size estimate will follow once every realization is shown to resolve.

\subsection{Recovering every edge from its histogram}\label{uniform:sec:decoding}

To prove that the constructed selection resolves the graph, we
recover an edge from its histogram. The last occupied level
determines its depth, and the remaining levels recover the endpoints
through separate counts, a Sidon pair sum, or the mixed coordinates
listed in Table~\ref{uniform:tab:decoding}.

\begin{table}[H]
\centering\small
\caption{Recovery after the depth is known. The three cases distinguish
whether the endpoint counts can be read separately or first appear as a sum.}
\label{uniform:tab:decoding}
\begin{tabular}{@{}p{1.5cm}p{4.5cm}p{8.5cm}@{}}
\toprule
Case & Information recovered & How it identifies the edge\\
\midrule
\(\delta\ge2\) & \(u_i,v_i\), then \(u_j,v_j\) &
Read the nearer endpoint from~\eqref{uniform:eq:near}, then the farther
one from~\eqref{uniform:eq:far} or~\eqref{uniform:eq:boundary}.\\[5pt]
\(\delta=0\) & \(D_i+D_j\) &
The Sidon property identifies the unordered pair. Its central edge is unique.\\[5pt]
\(\delta=1\) & \(u_i,v_j,v_i+u_j\), \(2u_jv_j\bmod q\) &
Equation~\eqref{uniform:eq:even} gives these four values.
Divide the fourth by \(2v_j\ne0\) in \(\F_q\) to recover \(u_j\),
then subtract from the third to recover \(v_i\).
The ordered pair fixes the central position.\\
\bottomrule
\end{tabular}
\end{table}

\begin{proposition}\label{uniform:prop:decode}
Every selection defined by~\eqref{uniform:eq:marks}, using any matrices with the margins~\eqref{uniform:eq:degrees}, resolves \(S_L(K_n)\).
\end{proposition}
\begin{proof}
We first recover the depth \(a\) of an edge. By Table~\ref{tab:distances}, every landmark is at distance at most \(L+a+2\).
The bounds in~\eqref{uniform:eq:balance} give at least \(nm\) landmarks of depth two, while the supports sharing \(i\) or \(j\) contain at most \(4\Delta=12m\) such landmarks. Since \(n>12\), a depth-two landmark exists on a disjoint support. Consequently,
\begin{equation}\label{uniform:eq:last}
\max\{t:H_e^W(t)>0\}=L+a+2.
\end{equation}
It remains to distinguish edges at the same \(a\).

We repeatedly use the following elementary observation. If \(y=3x+C+\xi\), where \(C\) is known and \(\xi\) lies in a known interval of three consecutive integers, then \(y\) determines the integer \(x\). The intervals for consecutive values of \(x\) are disjoint.

Write \(\eta_t=\eta_{ij}(t)\), with value zero at positions outside \(1,2,L-2,L-1\), and \(D_i(t)=0\) at inactive positions. There are three cases.

\smallskip\noindent\emph{Case 1: \(\delta=b-a\ge2\).}
For \(s=1,2\), Table~\ref{tab:distances} gives
\begin{equation}\label{uniform:eq:near}
H_e^W(a+s)=D_i(s)-\eta_s+\eta_{2a+s+1}.
\end{equation}
The paths from \(i\) supply \(D_i(s)-\eta_s\); the supporting path can supply the displayed additional bit. Other supports have larger distances. The error is in \([-1,1]\). Therefore these layers recover \(u_i,v_i\), and hence \(i\).

If \(a\ge1\), the next useful layers are
\begin{equation}\label{uniform:eq:far}
H_e^W(b+s)=D_j(s)+D_i(\delta+s)-\eta_{L-s}-\eta_{\delta+s},
\qquad s=1,2.
\end{equation}
These layers precede contributions from disjoint supports. Contributions from the supporting path itself vanish, since \(b+s>b\), its largest edge-to-vertex distance on that path. After subtracting the known \(D_i(\delta+s)\), the remaining error is in \([-2,0]\). The two coordinates of \(j\) are therefore recovered.

If \(a=0\), the second layer in~\eqref{uniform:eq:far} would receive contributions from disjoint supports. Instead use
\begin{align}
H_e^W(L)&=D_j(1)-\eta_{L-1},\notag\\
H_e^W(L+1)&=T_1-D_i(1)-D_i(L-1)-D_j(1)+D_j(2)
+\eta_{L-1}-\eta_{L-2}.\label{uniform:eq:boundary}
\end{align}
The first equation recovers \(u_j\), so \(D_j(1)\) is known. After moving the other known terms in the second equation, the remaining error is in \([-1,1]\), recovering \(v_j\).
Thus the histogram identifies the ordered endpoints and the position.

\smallskip\noindent\emph{Case 2: \(\delta=0\).}
Here \(L=2h+1\) and the edge is central. For \(s=1,2\), put
\(\gamma_{ij,s}=\eta_{ij}(s)+\eta_{ij}(L-s)\), the number of selected
vertices of depth \(s\) on its own support. For each active position
\(t\in\{1,2,L-2,L-1\}\), put
\[
 X_{ij,t}=D_i(t)+D_j(t)-\eta_{ij}(t)-\eta_{ij}(L-t).
\]
This counts landmarks at that position on paths sharing one endpoint,
with \(ij\) excluded. The histogram identity~\eqref{eq:central} records
\(\gamma_{ij,s}\) at distance \(h-s\) and \(X_{ij,t}\) at distance
\(h+t\); these levels are distinct. Since
\[
D_i(t)+D_j(t)=X_{ij,t}+\gamma_{ij,\min(t,L-t)}
\]
at each active position, it determines \(D_i+D_j\). Lemma~\ref{uniform:lem:robust} identifies the unordered support, which contains exactly one central edge.

\smallskip\noindent\emph{Case 3: \(\delta=1\).}
Here \(L=2h\), \(h\ge3\), and \(a=h-1,b=h\). Directly from Table~\ref{tab:distances},
\begin{align}
H_e^W(h)&=D_i(1)-\eta_1,\notag\\
H_e^W(h+1)&=D_i(2)+D_j(1)-\eta_2-\eta_{L-1},\notag\\
H_e^W(h+2)&=D_j(2)-\eta_{L-2},\notag\\
H_e^W(3h-1)&=D_j(L-1)-\eta_1.\label{uniform:eq:even}
\end{align}
For the last equation, only landmarks at position \(L-1\) on paths leaving \(j\) reach that layer; landmarks on disjoint supports begin at \(3h\).
The first and third equations recover \(u_i,v_j\), and the second recovers the integer \(v_i+u_j\).
The last recovers the fourth code coordinate \(2u_jv_j\bmod q\).
Indeed, its total correction \(\varepsilon_{j,4}-\eta_1\) lies in
\([-1,1]\) when \(\sigma_4=1\), in \([-2,0]\) when \(\sigma_4=-1\), and in \([-1,0]\) when \(\sigma_4=0\). Each is a known interval of width at most two.

Since \(v_j\ne0\), division by \(2v_j\) in \(\F_q\) gives \(u_j\).
The integer sum already recovered then gives \(v_i\). The ordered support and edge position are determined. This explains the nonzero second coordinate imposed in~\eqref{uniform:eq:code}.
All three cases identify the support and position once the depth is known.
Together with the size estimate~\eqref{uniform:eq:size}, this proves
Theorem~\ref{thm:uniform}.
\end{proof}