\section{The two shortest subdivisions}\label{sec:short}
Increasing a replacement path from two to three edges gives each
support two independently selectable internal vertices. We show how
this changes the answer from impossibility to existence for every
order. In the matrix description, the single shared selection at
length two imposes symmetry; length three permits different entries
in the two directions. The first part proves that symmetry forces a
collision. The remaining parts construct the nonsymmetric matrices
and complete their finite verification.

\subsection{Length two: every selection leaves a collision}\label{sec:two}
At length two, the two directions of a support share the same internal
landmark choice. We show that this symmetry forces a collision by
encoding a selection as a symmetric binary matrix and comparing its
row sums.

\begin{theorem}\label{short:thm:two}
For every integer \(n\ge3\), \(\edimm(S_2(K_n))=\infty\).
\end{theorem}
The proof follows in this subsection, after
Lemmas~\ref{short:lem:repeated} and~\ref{short:lem:threshold}.
The first finds a collision when two adjusted degrees coincide; the
second gives an explicit matrix form for the remaining case.

Write \(v_0,\ldots,v_{n-1}\) for the original vertices, and \(w_{ij}=w_{ji}\)
for the vertex inserted on \(v_iv_j\). Thus \(w_{ij}=x_{ij}(1)\),
and we abbreviate its selection indicator \(\eta_{ij}(1)\) to
\(\eta_{ij}\) throughout the length-two argument. Every edge is \(e_{ij}=v_iw_{ij}\)
for a unique ordered pair \(i\ne j\). For an arbitrary landmark set \(W\), put
\[
 \alpha_i=\ind_{\{v_i\in W\}},\quad \eta_{ij}=\ind_{\{w_{ij}\in W\}},\quad
 d_i=\sum_{j\ne i}\eta_{ij},\quad A_0=\sum_i \alpha_i,\quad B=\sum_{i<j}\eta_{ij}.
\]
The counts of selected vertices at distances \(0,1,2,3\) from \(e_{ij}\) are
\begin{equation}\label{short:eq:twohist}
 (\alpha_i+\eta_{ij},\ \alpha_j+d_i-\eta_{ij},\
 A_0-\alpha_i-\alpha_j+d_j-\eta_{ij},\ B-d_i-d_j+\eta_{ij}).
\end{equation}
For example, the vertices at distance one are \(v_j\) and the \(w_{ik}\)
with \(k\notin\{i,j\}\); at distance three they are precisely the
\(w_{k\ell}\) with support disjoint from \(\{i,j\}\).
Put \(t_i=d_i+\alpha_i\) and \(r_i=d_i-\alpha_i\).
Equality of the histograms in~\eqref{short:eq:twohist} is equivalent to equality of
\begin{equation}\label{short:eq:two_code}
 \Gamma(i,j)=(\alpha_i+\eta_{ij},\ t_i+\alpha_j,\ r_j).
\end{equation}
Indeed, a triple \((x,y,z)\) recovers the histogram as
\((x,y-x,A_0+z-x,B-y-z+x)\).

\begin{lemma}\label{short:lem:repeated}
If \(t_u=t_v\) for distinct \(u,v\), then two distinct edges have equal
distance multisets.
\end{lemma}
\begin{proof}
If \(\alpha_u=\alpha_v\), then \(d_u=d_v\) and \(r_u=r_v\), so
\(\Gamma(u,v)=\Gamma(v,u)\).
Otherwise interchange the indices to have \(\alpha_u=0,\alpha_v=1\).
Then \(d_u=d_v+1\), whence
\[
 \sum_{j\notin\{u,v\}}(\eta_{uj}-\eta_{vj})=1.
\]
For some such \(j\), \(\eta_{uj}=1,\eta_{vj}=0\), and~\eqref{short:eq:two_code}
gives \(\Gamma(u,j)=\Gamma(v,j)\).
\end{proof}

The remaining case is described by the following matrix form of
Aguilar's classification~\cite[Theorem~2.1]{aguilar}. The diagonal entries
represent loops counted once in each degree.

\begin{lemma}\label{short:lem:threshold}
Let \(M\) be a symmetric binary matrix of order \(n\) with distinct row sums.
After possibly replacing \(M\) by its entrywise complement and simultaneously
ordering its rows and columns, its entries are
\[
 M_{ij}=\ind_{\{i+j\geq n\}},\qquad 0\leq i,j<n.
\]
\end{lemma}
\begin{proof}
The \(n\) distinct row sums belong to \(\{0,\ldots,n\}\).
A zero row and an all-ones row cannot coexist in a symmetric matrix.
Thus the row sums are either \(0,\ldots,n-1\) or \(1,\ldots,n\).
Complement if necessary, and order them increasingly.
Row zero vanishes. Row \(n-1\) is one except in column zero.
Deleting these two rows and columns leaves row sums \(0,\ldots,n-3\).
Induction, starting with orders one and two, gives the stated formula.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{short:thm:two}]
Repeated values of \(t_i\) are covered by Lemma~\ref{short:lem:repeated}.
In the remaining case, apply Lemma~\ref{short:lem:threshold} to the symmetric matrix whose
diagonal is \(\alpha_i\) and whose off-diagonal entries are \(\eta_{ij}\).
Complementation is legitimate: the full vertex set gives every edge the
same histogram
\[
 \left(2,n-1,2n-4,\binom{n-2}{2}\right),
\]
so complementing \(W\) preserves every collision.

We may consequently assume
\[
 t_i=i,\qquad \alpha_i=\ind_{\{2i\geq n\}},\qquad
 \eta_{ij}=\ind_{\{i+j\geq n\}},\qquad r_i=i-2\alpha_i.
\]
For \(n=3,4\), substitution into~\eqref{short:eq:two_code} gives
\(\Gamma(0,2)=\Gamma(1,0)=(0,1,0)\).
For \(n\geq5\), put \(h=\lceil n/2\rceil\). Then \(h\geq3\),
\(h+1\leq n-1\), and
\[
 \Gamma(0,h+1)=\Gamma(1,h-1)=(0,1,h-1).
\]
Indeed, both first coordinates vanish, both second coordinates equal one,
and \(r_{h+1}=r_{h-1}=h-1\). These are valid distinct edges.
Complementation transfers the collision back to the original landmark set
when needed.
\end{proof}


Distinct row sums still leave two edges indistinguishable.
For \(n=6\), Fig.~\ref{fig:two-matrix} follows the entries and row sums
that produce their common record.
\begin{figure}[htbp]
\centering\input{figures/length_two_matrix.tex}
\caption{From landmark bits to a collision at length two, for \(n=6\).
In (a), the adjacent columns give \(t_i=i\), \(\alpha_i=M_{ii}\), and
\(r_i=i-2\alpha_i\). In (b), the cells \((0,4)\) and \((1,2)\) give
the internal-vertex bits \(\eta_{04}\) and \(\eta_{12}\); the highlighted
edges are \(e_{04}=v_0w_{04}\) and \(e_{12}=v_1w_{12}\).
Substitution from (a) gives \(\Gamma(0,4)=\Gamma(1,2)=(0,1,2)\).
Here \(A_0=3\) and \(B=6\), so~\eqref{short:eq:two_code} gives the common
histogram \((0,1,5,3)\), ordered by distances zero through three.}
\label{fig:two-matrix}
\end{figure}

For \(n=2\), the graph is a path and an endpoint resolves its edges.
Thus the restriction \(n\geq3\) is sharp.

\FloatBarrier

\subsection{Length three: encode the landmarks by a matrix}\label{sec:three-matrix}
The two internal vertices on each support can now be selected
independently. We encode this freedom in a binary matrix and express
the edge histograms through its row sums, column sums and diagonal,
so that conditions on these quantities will ensure that all edges
are distinguished. Fig.~\ref{fig:matrix-landmarks} illustrates
this encoding with an order-five matrix from the CSV data and its ten
landmarks.
Write each replacement path as \(v_i-x_{ij}-x_{ji}-v_j\), where
\(x_{ij}=x_{ij}(1)\). In this length-three argument, abbreviate
\(\eta_{ij}(1)\) to \(\eta_{ij}\); now \(\eta_{ij}\) and \(\eta_{ji}\)
refer to two different vertices. Set
\[
 \alpha_i=\ind_{\{v_i\in W\}},\quad \eta_{ij}=\ind_{\{x_{ij}\in W\}},\quad
 p_i=\sum_{j\ne i}\eta_{ij},\quad q_i=\sum_{j\ne i}\eta_{ji},\quad
 A_0=\sum_i \alpha_i,\quad B=\sum_i p_i.
\]
Here \(p_i,q_i\) are integers; the letter \(p\) without a subscript will
denote a prime. Denote terminal edges by \(T_{ij}=v_ix_{ij}\), for ordered
pairs \(i\ne j\), and middle edges by \(E_{ij}=x_{ij}x_{ji}\), for
unordered pairs \(\{i,j\}\). Put \(s_{ij}=\eta_{ij}+\eta_{ji}\).
It is convenient to encode \(W\) by a full binary matrix \(M\), allowing
its diagonal to be nonzero:
\begin{equation}\label{short:eq:matrix_encoding}
 \alpha_i=M_{ii},\qquad \eta_{ij}=M_{ij}\ (i\ne j),\qquad
 R_i=\sum_j M_{ij}=p_i+\alpha_i,\qquad
 Q_i=\sum_j M_{ji}=q_i+\alpha_i.
\end{equation}
Every entry equal to one selects exactly one vertex. Hence
\(|W|=\sum_iR_i\). The diagonal entries correspond to original vertices.




\begin{figure}[H]
\centering\input{figures/matrix_landmarks.tex}
\caption{From a matrix to unnamed distances. In (a), a binary matrix
of order five selects ten landmarks. Its row and column sums are shown
in the margins. Diagonal ones select originals;
off-diagonal ones select the corresponding internal vertices.
In (b), the path from \(v_1\) to \(v_4\) illustrates four entries;
filled vertices are selected. In (c) and (d), the histograms of
\(T_{14}\) and \(E_{14}\) count distances to all ten landmarks encoded
by the matrix. Both have total mass ten, and their multiplicities
distinguish these two edges; distance five already separates their
types in this example. The CSV certificate checks all edge pairs.}\label{fig:matrix-landmarks}
\end{figure}

The two histograms, ordered by distance from zero to five, are
\begin{align}
 H_T(i,j)=\bigl(&\alpha_i+\eta_{ij},\ p_i-\eta_{ij}+\eta_{ji},\
 \alpha_j+q_i-\eta_{ji},\notag\\[-2pt]
 &A_0-\alpha_i-\alpha_j+p_j-\eta_{ji},\
 B-p_i-q_i-p_j+\eta_{ji},\ 0\bigr),\label{short:eq:terminal}\\
 H_E(i,j)=\bigl(&s_{ij},\ \alpha_i+\alpha_j,\
 p_i+p_j-s_{ij},\ q_i+q_j-s_{ij},\notag\\[-2pt]
 &A_0-\alpha_i-\alpha_j,\
 B-p_i-p_j-q_i-q_j+s_{ij}\bigr).\label{short:eq:middle}
\end{align}
For a terminal edge, distance zero selects its two endpoints; distance one
selects \(x_{ji}\) and the other \(x_{ik}\); distance two selects \(v_j\)
and the other \(x_{ki}\); distance three selects the remaining original
vertices and the \(x_{jk}\) with \(k\ne i,j\). The remaining internal
vertices have distance four.
For a middle edge, the two originals have distance one, the other
internals near these originals have distance two, their partners have
distance three, the other originals have distance four, and internals
supported outside \(\{i,j\}\) have distance five. This proves both formulas.

We seek matrices satisfying
\begin{equation}\label{short:eq:target}
 R_i=i,\qquad 2Q_i-\alpha_i\equiv f(i)+d\pmod p,\qquad
 f(i)=\frac{i(i+3)}2,\quad 0\le i<n,
\end{equation}
where \(p\ge n+5\) is prime and \(d\in\{0,\ldots,p-1\}\)
is a common shift. Throughout this construction, \(x\bmod p\)
denotes the representative in \(\{0,\ldots,p-1\}\) of an integer \(x\).
The pair \((i,f(i))\) lies on an affine image of the Sidon parabola.
The added linear term makes its consecutive differences \(i+2\),
which will also distinguish terminal edges.
\begin{proposition}\label{short:prop:separation}
Let \(n\ge7\), let \(p\ge n+5\) be prime, and suppose a binary matrix
has row sums \(R_i=i\), column sums \(Q_i\), and diagonal \(\alpha_i\) satisfying
\eqref{short:eq:target} for some \(d\). The corresponding landmark set resolves
\(S_3(K_n)\) and has size \(n(n-1)/2\).
\end{proposition}
\begin{proof}
Interpret the matrix using~\eqref{short:eq:matrix_encoding}.
Every entry equal to one selects one vertex, so
\(|W|=\sum_iR_i=n(n-1)/2\).

\emph{Middle edges.}
Equation~\eqref{short:eq:middle} recovers \(\alpha_i+\alpha_j\), \(R_i+R_j=i+j\),
and \(Q_i+Q_j\).
It therefore recovers \(i+j\) and \(f(i)+f(j)+2d\) modulo \(p\).
The latter quantity, together with \(i+j\), determines
\(i^2+j^2\), then \(ij\), and hence the unordered pair
\(\{i,j\}\). Here \(p\) is odd, and the labels \(0,\ldots,n-1\)
are distinct modulo \(p\). Thus all middle edges are distinguished.

\emph{Terminal edges with a common origin.}
The sum of the first two entries of~\eqref{short:eq:terminal} is \(i+\eta_{ji}\),
so it identifies \(\eta_{ji}\) for fixed \(i\).
The third entry then identifies \(\alpha_j\), and the fourth, which equals
\(A_0+j-\alpha_i-2\alpha_j-\eta_{ji}\), identifies \(j\).

\emph{Terminal edges with different origins.}
Suppose \(H_T(i,j)=H_T(u,v)\) with \(i<u\).
The sum of the first two entries forces \(u=i+1\), \(\eta_{ji}=1\),
and \(\eta_{vu}=0\).
Set \(\Delta_1=\alpha_u-\alpha_i\) and
\(\Delta_2=\alpha_j-\alpha_v\).
The other equalities give
\[
 Q_u-Q_i=\Delta_1+\Delta_2-1,\qquad
 j-v=1-\Delta_1+2\Delta_2.
\]
Writing \(Z_i=2Q_i-\alpha_i\), a collision consequently requires
\(Z_u-Z_i=\Delta_1+2\Delta_2-2\in\{-5,-4,\ldots,1\}\).
The value \(-5\) forces \(\Delta_1=\Delta_2=-1\) and \(j=v\), contradicting
\(\Delta_2=-1\). Hence the difference must lie in
\(\{-4,-3,-2,-1,0,1\}\).
On the other hand,~\eqref{short:eq:target} implies
\[
 Z_{i+1}-Z_i\equiv f(i+1)-f(i)=i+2\pmod p.
\]
The residue \(i+2\) belongs to \(\{2,\ldots,n\}\), which is disjoint from
\(\{p-4,p-3,p-2,p-1,0,1\}\), because \(p\ge n+5\).
This excludes every terminal-edge collision.

\emph{Separating the two types.}
For any middle support \(\{i,j\}\), one of the three largest row
indices \(k\) is outside this support.
Its internal outdegree is \(p_k=k-\alpha_k\ge n-4\ge3\).
At most two of its selected vertices \(x_{k\ell}\) have
\(\ell\in\{i,j\}\). At least one is therefore supported entirely
outside \(\{i,j\}\), and is at distance five from the middle edge.
Every terminal histogram has distance-five coordinate zero.
This proves that \(W\) resolves all edges.
\end{proof}
\subsection{Producing the matrix margins}\label{sec:three-balance}
The remaining task is to make the column sums add up to
\(N=0+1+\cdots+(n-1)=n(n-1)/2\), while keeping enough room for a
chosen diagonal. Each residue produced by \(f(i)+d\) offers two choices. Write
\(p=2m+1\).
For a shift \(d\), put
\begin{equation}\label{short:eq:low}
 r_i=(f(i)+d)\bmod p\in\{0,\ldots,2m\},\qquad
 L_i=\lceil r_i/2\rceil,\qquad \alpha_i^0=r_i\bmod2.
\end{equation}
The low choice \((Q_i,\alpha_i)=(L_i,\alpha_i^0)\) satisfies \(2Q_i-\alpha_i=r_i\).
The high choice is
\begin{equation}\label{short:eq:lift}
 Q_i=L_i+m+1-\alpha_i^0,\qquad \alpha_i=1-\alpha_i^0,
\end{equation}
and satisfies \(2Q_i-\alpha_i=r_i+p\).
Thus the column increases by \(m\) at odd residues and by \(m+1\)
at even residues.

Start with all low choices. If their sum is \(S\), the deficit is \(D=N-S\).
Raising \(X\) odd-residue columns and \(Y\) even-residue columns gives
the exact balance precisely when
\[
 D=mX+(m+1)Y.
\]
We choose the smallest eligible low values in each class, ordered by
\((L_i,i)\), and leave index zero unraised. This moves the columns
towards the middle of their possible range. The resulting concentration
provides room in the matrix inequalities, even after the diagonal is fixed.
The relevant error is controlled by the quadratic character
\(\chi:\mathbb Z\to\{-1,0,1\}\) modulo \(p\): it is \(0\) on multiples
of \(p\), \(1\) on nonzero squares modulo \(p\), and \(-1\) otherwise.
An interval bound \(C_\chi\ge0\) means that
\[
 \left|\sum_{j=u+1}^{u+\ell}\chi(j)\right|\le C_\chi
 \qquad(u\in\mathbb Z,\quad \ell\in\{0,\ldots,p\}).
\]
The character is periodic, so this includes intervals that wrap modulo
\(p\). Appendix~\ref{app:three} proves the following quantitative statement.

\begin{proposition}\label{short:prop:quadratic_matrix}
Let \(p=2m+1\) be prime, let \(n=p-g\), and suppose \(g\ge5\) and
\(m\ge150\). If the quadratic character modulo \(p\) has absolute sum
at most \(C_\chi\) on every interval of residues and
\begin{equation}\label{short:eq:effective_condition}
 H:=C_\chi+g+2\le m/12,
\end{equation}
then a binary matrix satisfying~\eqref{short:eq:target} exists.
The shift \(d\) can be chosen even in \([m/2,3m/2]\), with \(\alpha_0=0\).
\end{proposition}

The proof in Appendix~\ref{app:three} first uses
Lemma~\ref{short:lem:diagonal} to quantify the room needed for the
chosen diagonal. Varying the modular shift then makes the column
total match the row total, as illustrated in
Fig.~\ref{fig:residue-walk}. Lifting the smallest columns preserves
enough room in every matrix cut. Fig.~\ref{short:fig:distribution}
illustrates the concentration mechanism; the tail estimates in
Appendix~\ref{app:three} establish the required finite bounds.

Dusart's prime-gap estimate and Lapkova's character-sum estimate imply
these hypotheses for every \(n\ge10\,000\)
(Corollary~\ref{short:cor:threshold}). Exact certificates cover all
remaining orders in Section~\ref{sec:certificates}.
Corollary~\ref{cor:three-lower} supplies the lower bound in the theorem
below. Together these results give:
\begin{theorem}\label{short:thm:three}
For every \(n\ge3\),
\[
 \edimm(S_3(K_n))\le\binom n2.
\]
For \(n\ge10\), the lower bound is \(n^2/16-n/2\). Consequently
\(\edimm(S_3(K_n))=\Theta(n^2)\) as \(n\to\infty\).
\end{theorem}