\documentclass[11pt,a4paper]{article}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[margin=27mm]{geometry}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{booktabs,array,enumitem,microtype}
\usepackage{needspace}
\usepackage{fancyhdr}
\pagestyle{fancy}
\fancyhf{}
\fancyhead[L]{\small Four-cycle supersaturation and polarity stability}
\fancyhead[R]{\small\thepage}
\setlength{\headheight}{14pt}
\usepackage[dvipsnames]{xcolor}
\usepackage{hyperref}
\hypersetup{colorlinks=true,linktoc=all,linkcolor=MidnightBlue,citecolor=MidnightBlue,
urlcolor=MidnightBlue,
pdftitle={Four-cycle supersaturation and polarity stability at q-squared plus q vertices},
pdfauthor={Zhenyu Sun}}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{question}[theorem]{Question}
\DeclareMathOperator{\ex}{ex}
\DeclareMathOperator{\diam}{diam}
\newcommand{\Nfour}{N_{C_4}}
\setlist{itemsep=3pt,topsep=5pt}
\allowdisplaybreaks[2]
\numberwithin{equation}{section}
\setcounter{tocdepth}{1}
\title{Four-cycle supersaturation and polarity stability\\
at \(q^2+q\) vertices}
\author{Zhenyu Sun}
\date{}
\begin{document}
\maketitle
\begin{abstract}
Let $m_0=\frac12q(q+1)^2-q$. For every even $q\ge1600$, we
prove that a graph on $q^2+q$ vertices with at least $m_0+1$ edges
contains at least $\lceil(q-1)/12\rceil$ four-cycles. For powers
of two in this range, $m_0$ is the extremal number and a polarity
construction has exactly $q-1$ four-cycles at $m_0+1$ edges.
These bounds determine the order of magnitude of the minimum
count on this sequence. We also prove a stability theorem: for
every nonnegative integer $b$ and every even
$q\ge10^{18}(b+1)^{16}$, each $C_4$-free graph on $q^2+q$
vertices with $m_0-b$ edges is a spanning subgraph of an
orthogonal polarity graph with one point deleted. The required
degree bounds follow from the edge count. As a consequence, a
graph on $q^2+q$ vertices with $m_0+1$ edges has at least $q-1$
four-cycles if an edge set of size $t\ge1$ meets every four-cycle
and $q$ is even with $q\ge10^{18}t^{16}$. The counting proof uses a codegree
commutator; the stability proof combines degree-deficit
concentration with incidence completion and polarity extension.
\end{abstract}
\medskip
\noindent\textbf{Keywords.}
Four-cycle; supersaturation; extremal graph; polarity graph;
projective plane; stability.

\tableofcontents
\clearpage

\section{Introduction}
\label{sec:introduction}

For a graph $F$, let $\ex(n,F)$ be the largest number of edges in
an $n$-vertex graph containing no copy of $F$.
Write $\Nfour(G)$ for the number of unlabelled, not necessarily
induced, four-cycles in $G$, and define
\[
 h(n)=\min\{\Nfour(G):|V(G)|=n,\ e(G)=\ex(n,C_4)+1\}.
\]
The first edge above an extremal bound is a basic case of
supersaturation \cite{ErdosSimonovits1983}.
A conjecture of Erd\H{o}s and Simonovits predicts
$h(n)\ge(1-o(1))\sqrt n$ \cite[Conjecture~1]{ErdosSimonovits1984}.
We determine the order of magnitude of $h(n)$ on the sequence
$n=q^2+q$, where $q$ is a power of two, and establish a quantitative
structure theorem for $C_4$-free graphs just below the corresponding
edge bound.

Throughout, put
\begin{equation}
 N=q^2+q+1,\qquad M=\frac12q(q+1)^2,\qquad
 n=N-1,\qquad m_0=M-q.
 \label{eq:parameters}
\end{equation}
The equality $\ex(n,C_4)=m_0$ is known for powers of two
\cite{FirkeEtAl2013}.
Our statements for general even $q$ use the numerical edge count
$m_0$; the conclusions about $h(n)$ use this known equality.

\subsection{Main results}

\begin{theorem}[Supersaturation at the adjacent order]
\label{thm:main}
Let $q\ge1600$ be even. Every graph $G$ with
\[
 |V(G)|=q^2+q,\qquad e(G)\ge m_0+1
\]
satisfies
\[
 12\Nfour(G)\ge q-1.
\]
\end{theorem}

Deleting an absolute point from a classical orthogonal polarity
graph and adding an edge between two remaining absolute points
gives exactly $q-1$ four-cycles. This construction and the known
extremal number yield the following consequence.

\begin{corollary}
\label{cor:order-of-magnitude}
For every power of two $q\ge2048$,
\[
 \left\lceil\frac{q-1}{12}\right\rceil
 \le h(q^2+q)\le q-1.
\]
In particular, $h(q^2+q)=\Theta(q)$ on this sequence.
\end{corollary}

Our second main result describes the graphs below the same edge
bound. A polarity of a projective plane is an incidence-reversing
involution between points and lines. Its simple polarity graph
joins distinct points $x,y$ when $x$ lies on the polar line of $y$.
A point is absolute if it lies on its polar line, and a polarity
of a plane of order $q$ is orthogonal if it has exactly $q+1$
absolute points.

\begin{theorem}[Polarity stability]
\label{stab:main}
Let $b\ge0$ be an integer and let $q$ be even with
\[
 q\ge10^{18}(b+1)^{16}.
\]
Every $C_4$-free graph $F$ with $q^2+q$ vertices and $m_0-b$
edges is a spanning subgraph of $P-p$, where $P$ is the simple
graph of an orthogonal polarity of a projective plane of order
$q$ and $p$ is one of its points.
The absolute points of this polarity form a line.
More precisely, $F$ is obtained from $P-p$ by deleting $b$ edges
when $p$ is absolute, and by deleting $b-1$ edges when $p$ is
nonabsolute.
\end{theorem}

The containing plane need not be Desarguesian.
The estimate is uniform in $q$ and $b$ under the displayed condition.
It includes every fixed deficit $b$ for all sufficiently large even
$q$, and allows $b$ to grow subject to
$b+1\le(q/10^{18})^{1/16}$.

\subsection{Relation to earlier work}
\label{subsec:related-work}

F\"uredi proved $\ex(N,C_4)=M$ for powers of two
\cite{Furedi1983}.

Firke, Kosek, Nash, and Williford
\cite[Theorem~1]{FirkeEtAl2013} proved
$\ex(N-1,C_4)\le m_0$ for every even $q$, with equality
when $q$ is a power of two. For the equality case and sufficiently large even $q$, the
absolute-point deletion classification was announced in their
Theorem~2.
Theorem~\ref{struct:all-extremal-core-recognition} gives a
complete proof at the edge count $m_0$, with the explicit
sufficient condition $q\ge10^{15}$.

At order $N$, He, Ma, and Yang
\cite[Theorem~1.3]{HeMaYang2021} proved that, for even
$q\ge10^{12}$, every graph with $M+1$ edges has at least
$q-1$ four-cycles. They also characterized the graphs with
fewer than $2q-3$ four-cycles. In particular,
$h(N)=q-1$ for $q=2^k$ with $k\ge40$.
Their subsequent stability theorem
\cite[Theorem~3.1]{HeMaYang2023} states that, for each fixed
$0<c<1$ and every sufficiently large even $q$, every
$C_4$-free graph on $N$ vertices with at least $M-cq/2$
edges is contained in a unique polarity graph of order $q$.
Table~\ref{tab:related-results} compares these results with
the two principal theorems of the present paper.

\begin{table}[htbp]
\centering
\small
\setlength{\tabcolsep}{4pt}
\renewcommand{\arraystretch}{1.18}
\begin{tabular}{@{}
  >{\raggedright\arraybackslash}p{0.25\textwidth}
  >{\centering\arraybackslash}p{0.08\textwidth}
  >{\raggedright\arraybackslash}p{0.29\textwidth}
  >{\raggedright\arraybackslash}p{0.31\textwidth}@{}}
\toprule
Result & Order & Hypothesis & Conclusion \\
\midrule
Firke et al.\ \cite[Theorem~1]{FirkeEtAl2013}
  & $N-1$ & $C_4$-free
  & $e(G)\le m_0$ \\[3pt]
He--Ma--Yang \cite[Theorem~1.3]{HeMaYang2021}
  & $N$ & $e(G)=M+1$
  & $\Nfour(G)\ge q-1$ \\[3pt]
He--Ma--Yang \cite[Theorem~3.1]{HeMaYang2023}
  & $N$ & $C_4$-free; $e(G)\ge M-cq/2$
  & Unique containing polarity graph \\[3pt]
Theorem~\ref{thm:main}
  & $N-1$ & $e(G)\ge m_0+1$
  & $12\Nfour(G)\ge q-1$ \\[3pt]
Theorem~\ref{stab:main}
  & $N-1$ & $C_4$-free; $e(F)=m_0-b$
  & $F\subseteq P-p$, with $P$ orthogonal \\
\bottomrule
\end{tabular}
\caption{Results at the two consecutive orders. The ranges of
$q,c,b$ are those specified in the text and in
Theorems~\ref{thm:main} and~\ref{stab:main}.}
\label{tab:related-results}
\end{table}

The change of order requires a completion argument.
Adjoining an isolated vertex to a graph covered by
Theorem~\ref{stab:main} gives
\[
 |V(F\cup K_1)|=N,\qquad
 e(F\cup K_1)=M-q-b<M-\frac c2q
 \quad(0<c<1).
\]
Its edge count is therefore below the hypothesis of the
existing $N$-vertex stability theorem. Adding edges at the
new vertex instead requires control of the four-cycles
they create.

For nearby orders with a larger vertex deficit, Ma and Yang
\cite[Theorem~1.3]{MaYang2023} proved
$\ex(N-r,C_4)\le M-0.92rq$ whenever $r$ is sufficiently
large and $r\le0.01q$, with no parity restriction on $q$.
Degree deficits, including negative values at vertices of
degree greater than $q+1$, already occur in that work
\cite[Definition~3.1]{MaYang2023}.
The signed moment and concentration estimates below develop
this counting method for the edge deficits $m_0-e(F)$
at the fixed order $N-1$.


\subsection{Sharp counting and structural refinements}

For a graph $G$, let $\tau_4(G)$ be the minimum number of edges
whose deletion makes $G$ $C_4$-free. The stability theorem gives
a sharp counting consequence.

\begin{corollary}[Sharp supersaturation with a small edge transversal]
\label{sharp:small-transversal}
Let $t\ge1$ be an integer, let $q$ be even with
\begin{equation}
 q\ge10^{18}t^{16},
 \label{sharp:threshold}
\end{equation}
and let $G$ have $q^2+q$ vertices and $m_0+1$ edges.
If $\tau_4(G)\le t$, then
\[
 \Nfour(G)\ge q-1.
\]
\end{corollary}

Deleting a transversal of $t$ edges leaves a $C_4$-free graph
at deficit $t-1$. Theorem~\ref{stab:main} embeds this graph in a
one-point deletion of a polarity graph. The single-edge estimates
of Proposition~\ref{prop:polarity-price} then give the conclusion;
the complete argument appears in Section~\ref{sec:applications}.

The degree control used in the stability proof is also quantitative.
If $F$ is $C_4$-free with $n$ vertices and $m_0-b$ edges, then,
for even $q$,
\[
 q\ge10^9(b+1)^8\quad\Longrightarrow\quad\Delta(F)\le q+1
\]
(Theorem~\ref{struct:automatic-fixed-deficit-cap}).
A preliminary result for $q\ge2048$ and $0\le b\le q/16$
gives $\Delta(F)\le q+2$, at most one vertex of degree $q+2$,
and minimum degree at least $q-b-2$.

At $b=0$, a separate two-vertex concentration argument improves
the sufficient threshold to $q\ge10^{15}$ and yields a unique
completion by the missing absolute point
(Theorem~\ref{struct:all-extremal-core-recognition}).
This classification also gives a sharp bound throughout a linear
range of edge modifications. If $G$ has $n$ vertices and $m_0+1$
edges and $F$ is a $C_4$-free graph on the same vertices with
$m_0$ edges, then, for even $q\ge10^{15}$,
\begin{equation}
 b=|E(F)\setminus E(G)|\le q-2
 \quad\Longrightarrow\quad
 \Nfour(G)\ge(b+1)(q-1-b)\ge q-1.
 \label{eq:intro-edit-bound}
\end{equation}
The proof counts cycles containing exactly one edge outside $F$.
For a fixed new edge, their supporting three-edge paths in $F$
are pairwise edge-disjoint, so each deleted edge removes at most
one of these cycles.

A further refinement concerns the full-degree surplus. With
$\delta_v=q+1-d_F(v)$, define
\begin{equation}
 \eta(F)=\sum_{v:d_F(v)=q+1}
 \left(\sum_{w\in N_F(v)}\delta_w-2\right).
 \label{eq:eta-definition}
\end{equation}
For even $q$, its summands are nonnegative in a $C_4$-free graph
on $n$ vertices.
Under $\Delta(F)\le q+1$, zero surplus at deficit $b$ forces
an absolute-point deletion at $b=0$ or a nucleus deletion at
$b=1$, once $q\ge8192(b+1)^4$.
The nucleus is the nonabsolute point whose polar line is the
absolute-point line.
At $b=1$, the sufficient threshold is $q\ge12$ under the same
degree bound. Section~\ref{sec:zero-depth} proves these refinements,
including uniqueness of the one-point completions.

\subsection{Proofs and organization}

The proof of Theorem~\ref{thm:main} is combinatorial.
The codegree matrix differs from $qI+J$ by the degree deficits,
the uncovered-pair matrix, and a nonnegative excess matrix
controlled by the number of four-cycles.
Commuting this identity with the adjacency matrix constrains
the unique uncovered partners of full-degree vertices.
Neighbourhood counts then treat all four possible maximum-degree
configurations. In the case of a unique vertex of degree $q+2$,
an injective pairing of vertices with no uncovered partner
sharpens the exceptional-set estimate and permits cancellation
of the excess codegree at the high vertex.

For Theorem~\ref{stab:main}, the edge count first forces the required
degree bounds. The total excess deficit is then either $O(b+1)$
or at least $q-O(b+1)$. The latter alternative supplies sufficiently
many full-degree vertices directly. In the former, first and second
moments concentrate local weight $q-O(b+1)$ in $2b+3$ vertices.
Deleting these vertices leaves enough complete neighbourhoods to
recover a projective plane. The incidence-completion theorem
eliminates the uncovered point pairs and embeds the resulting
incidence system in a plane. A symmetric-incidence argument extends
the resulting assignment to a polarity. Finally, a count of missing
edges restores every deleted vertex and every edge between them.
The uniform estimates needed in this construction are stated
explicitly in Section~\ref{stab:section} and
Appendix~\ref{inc:general-incidence-section}.

Section~\ref{sec:preliminaries} gives the counting identities,
polarity construction, and elementary geometric bounds.
Section~\ref{sec:supersaturation} proves
Theorem~\ref{thm:main}. Sections~\ref{struct:global-degree-cap-section}
and~\ref{stab:section} establish the automatic degree bounds and
prove Theorem~\ref{stab:main}.
Sections~\ref{sec:extremal-cores},
\ref{struct:extremal-core-recognition-section}, and
\ref{sec:zero-depth} develop the extremal and zero-surplus refinements.
Section~\ref{sec:applications} proves the sharp counting consequences.
The remaining sharp-count question is stated in
Section~\ref{sec:questions}.
Appendices~\ref{inc:general-incidence-section} and
\ref{geo:polarity-extension-section} contain the incidence-completion
and polarity-extension results used in the structural proofs.

% Source: sections/preliminaries.tex
\section{Preliminaries}
\label{sec:preliminaries}

All graphs are finite, simple, and undirected. We write $N_G(v)$
and $d_G(v)$ for the neighbourhood and degree of $v$, omitting
$G$ when the ambient graph is fixed. For disjoint vertex sets
$X,Y$, write $e(X,Y)$ for the number of edges with one endpoint
in each set. The parameters $N,M,n,m_0$ are as in
\eqref{eq:parameters}.

\subsection{Codegrees and degree deficits}
\label{sec:counting}

For a vertex $v$ and a set $X\subseteq V(G)$, write
$d_X(v)=|N(v)\cap X|$, and put $d(v)=|N(v)|$.
For the supersaturation estimates, put
\[
 n=q^2+q,\qquad
 m_0=\frac12q(q+1)^2-q,\qquad m_+=m_0+1,
 \qquad Q=\Nfour(G).
\]
Unless stated otherwise, $q$ is an integer with $q\ge2$.
For distinct vertices $u,v$, let
\[
 c_{uv}=|N(u)\cap N(v)|.
\]
Writing $x_+=\max\{x,0\}$, define
\begin{equation}
 \begin{aligned}
 \delta_v&=q+1-d(v),&
 a_v&=\sum_{w\in N(v)}\delta_w,\\
 \varepsilon_v&=\sum_{w\ne v}(c_{vw}-1)_+,&
 u_v&=|\{w\ne v:c_{vw}=0\}|.
 \end{aligned}
 \label{eq:deficit-notation}
\end{equation}
The deficits $\delta_v$ and their neighbourhood sums $a_v$ are allowed
to be negative.  A pair of distinct vertices is \emph{uncovered} if
its codegree is zero.  We consistently write
\[
 H=\{v:d(v)=q+1\},\qquad L=\{v:d(v)\le q\}.
\]

\begin{lemma}
\label{lem:codegree-identities}
Let $G$ have $q^2+q$ vertices, and let $Q_v$ be the number of
four-cycles containing $v$.  Then
\begin{align}
 Q_v&=\sum_{w\ne v}\binom{c_{vw}}2,
 &2Q&=\sum_{\{v,w\}\subseteq V(G)}\binom{c_{vw}}2,
 \label{eq:cycle-codegrees}\\
 \varepsilon_v&\le Q_v\le Q,
 &\sum_v\varepsilon_v&\le4Q,
 \label{eq:excess-budget}\\
 u_v&=-1+q\delta_v+a_v+\varepsilon_v.
 \label{eq:local-deficit}
\end{align}
If $e(G)=m_+$, then
\begin{equation}
 \sum_v\delta_v=2q-2.
 \label{eq:total-deficit}
\end{equation}
Let $A$ be the adjacency matrix, let $J$ be the all-ones matrix,
and define symmetric matrices $U,R$ with zero diagonal by
\[
 U_{uv}=\mathbf 1_{\{c_{uv}=0\}},\qquad
 R_{uv}=(c_{uv}-1)_+\qquad(u\ne v).
\]
Then
\begin{equation}
 A^2=qI+J-U-\operatorname{diag}(\delta_v)+R,
 \label{eq:codegree-matrix}
\end{equation}
and, with $[S,T]=ST-TS$,
\begin{equation}
 [A,U]_{uv}
 =(d(u)-d(v))(1-A_{uv})+[A,R]_{uv}.
 \label{eq:codegree-commutator}
\end{equation}
\end{lemma}

\begin{proof}
A four-cycle containing $v$ is determined by its vertex opposite $v$
and its two common neighbours with $v$.  This proves the first
identity in \eqref{eq:cycle-codegrees}; counting the two opposite
pairs of every four-cycle proves the second.
The inequalities in \eqref{eq:excess-budget} follow from
$(r-1)_+\le\binom r2$ for nonnegative integers $r$.

Counting two-edge paths starting at $v$ gives
\[
 n-1-u_v+\varepsilon_v
 =\sum_{w\ne v}c_{vw}
 =\sum_{w\in N(v)}(d(w)-1)
 =q\,d(v)-a_v.
\]
Substituting $n=q^2+q$ and $d(v)=q+1-\delta_v$ proves
\eqref{eq:local-deficit}.  The degree sum yields
\eqref{eq:total-deficit} when $e(G)=m_+$.

The off-diagonal entries of \eqref{eq:codegree-matrix} express
$c_{uv}=1-U_{uv}+R_{uv}$, and its diagonal entries express
$d(v)=q+1-\delta_v$.  Commuting this identity with $A$, and using
\[
 [A,J]_{uv}=d(u)-d(v),\qquad
 [A,\operatorname{diag}(\delta_v)]_{uv}
 =(d(u)-d(v))A_{uv},
\]
gives \eqref{eq:codegree-commutator}.
\end{proof}

For even $q$, call a vertex $v$ \emph{good} if
\[
 v\in H,\qquad \varepsilon_v=0,\qquad a_v=2,
\]
and denote the set of good vertices by $Z_0$.

\begin{lemma}
\label{lem:good-vertices}
Suppose that $q$ is even and $|V(G)|=q^2+q$.
Every vertex $v\in H$ with $\varepsilon_v=0$ satisfies $a_v\ge2$.
Every good vertex $v$ lies in no four-cycle and has a unique
uncovered partner $f(v)$; moreover, $vf(v)\in E(G)$.
For any two good vertices $u,v$,
\begin{equation}
 A_{u,f(v)}=A_{f(u),v}.
 \label{eq:good-commutator}
\end{equation}
If $u,w$ are good and $f(u)=w$, then $f(w)=u$ and $w$ is the
only good neighbour of $u$.
\end{lemma}

\begin{proof}
For $v\in H$ with $\varepsilon_v=0$, equation
\eqref{eq:local-deficit} gives $u_v=a_v-1\ge0$.
If $a_v=1$, then $c_{vw}=1$ for every $w\ne v$, contrary to
\[
 2e(G[N(v)])=\sum_{w\in N(v)}c_{vw}=q+1,
\]
since $q+1$ is odd.  Hence $a_v\ge2$.

If $v$ is good, then $u_v=1$, and
\eqref{eq:cycle-codegrees} gives $Q_v=0$.
If its unique uncovered partner were outside $N(v)$, the same
parity identity would again have right-hand side $q+1$.
Thus $vf(v)$ is an edge.
The row and column of $R$ at a good vertex are zero, and all good
vertices have the same degree.  Taking the $(u,v)$ entry of
\eqref{eq:codegree-commutator} therefore gives
\eqref{eq:good-commutator}.

If $f(u)=w$ and $w$ is good, symmetry of $U$ gives $f(w)=u$.
Suppose that $x\ne w$ is another good neighbour of $u$.
Equation \eqref{eq:good-commutator}, applied to $w,x$, yields
$A_{w,f(x)}=A_{u,x}=1$.
The vertices $u,x,f(x),w$ are distinct: $f(x)=u$ would contradict
$f(u)=w$, and $f(x)=w$ would contradict $f(w)=u$.
They form a four-cycle, contrary to $Q_u=0$.
\end{proof}


\subsection{\texorpdfstring{$C_4$}{C4}-free cores and full-degree surplus}

A \emph{core at deficit $b$} is a $C_4$-free graph $F$ on $n$ vertices
with $e(F)=m_0-b$, where $b\ge0$ is an integer.
An \emph{extremal core} means such a graph with $b=0$.
The degree sum and Lemma~\ref{lem:codegree-identities} give
\[
 \sum_v\delta_v=2q+2b,\qquad u_v=q\delta_v-1+a_v.
\]
For even $q$, Lemma~\ref{lem:good-vertices} gives $a_v\ge2$
at every full-degree vertex. The surplus in
\eqref{eq:eta-definition} is therefore
\[
 \eta(F)=\sum_{v\in H}(a_v-2)\ge0.
\]
When $\Delta(F)\le q+1$, the sets $H$ and $L$ partition
$V(F)$, and all deficits are nonnegative.
The extremal hypotheses used in Section~\ref{sec:extremal-cores}
are
\begin{equation}
 |V(F)|=q^2+q,\qquad e(F)=m_0,\qquad
 F\text{ is }C_4\text{-free},\qquad \Delta(F)\le q+1.
 \label{eq:core-hypotheses}
\end{equation}

\subsection{Polarity graphs and the upper construction}
\label{sec:polarities}

A projective plane of order \(q\) has \(q^2+q+1\) points
and the same number of lines.  Every point lies on \(q+1\)
lines, every line contains \(q+1\) points, and two distinct
points or lines determine a unique common incident object.
A polarity is an incidence-reversing involution that
interchanges points and lines.  A point \(x\) is absolute
if it lies on its polar line.  A polarity is orthogonal when it has
exactly $q+1$ absolute points.

Given a polarity \(\pi\), let \(H\) be its simple polarity
graph: distinct points \(x,y\) are adjacent precisely when
\(x\in\pi(y)\).  Index the incidence matrix by points,
using \(\pi(y)\) as the line indexed by \(y\).  The resulting
matrix \(B\) is symmetric and satisfies
\begin{equation}
 B\mathbf1=(q+1)\mathbf1,\qquad B^2=qI+J.
 \label{eq:polarity-incidence}
\end{equation}
If \(D=\operatorname{diag}(\alpha_x)\), where \(\alpha_x\)
indicates that \(x\) is absolute, then the adjacency matrix
of \(H\) is \(A=B-D\).  Thus
\begin{equation}
 d_H(x)=q+1-\alpha_x,\qquad
 (A^2)_{xy}=1-A_{xy}(\alpha_x+\alpha_y)\quad(x\ne y).
 \label{eq:polarity-codegrees}
\end{equation}
In particular, \(H\) is \(C_4\)-free, its absolute points
are independent, and every nonadjacent pair has a unique
common neighbour.

\begin{proposition}[Four-cycles created by one edge]
\label{prop:polarity-price}
\label{sharp:puncture-price}
Let $P$ be the simple polarity graph of a projective plane of
order $q\ge2$. For a nonedge $uv$, let $z$ be its unique common
neighbour in $P$, and let $\alpha_x$ indicate that $x$ is absolute.
Then
\begin{equation}
 \Nfour(P+uv)=q+1-\alpha_u-\alpha_v-\alpha_z.
 \label{eq:polarity-edge-count}
\end{equation}
For any point $p\notin\{u,v\}$, put $K=P-p$. Then
\begin{equation}
 \Nfour(K+uv)\ge q-2;
 \qquad
 \Nfour(K+uv)\ge q-1\quad\text{if $p$ is absolute}.
 \label{sharp:arbitrary-puncture-price}
\end{equation}
For each fixed added edge, the old edge sets of the resulting
four-cycles are pairwise disjoint, both in $P$ and in $K$.
\end{proposition}

\begin{proof}
Let $A$ be the adjacency matrix of $P$, put
$D=\operatorname{diag}(\alpha_x)$, and set $B=A+D$.
The incidence identities \eqref{eq:polarity-incidence} apply to $B$.
Since \(uv\) is a nonedge, every length-three walk from
\(u\) to \(v\) has distinct vertices.  Hence its number is
exactly \(\Nfour(P+uv)\).
Expand \(A^3=(B-D)^3\).  The terms containing \(B_{uv}\)
vanish.  By \eqref{eq:polarity-incidence},
\[
 (B^3)_{uv}=q+1,\qquad
 (B^2D)_{uv}=\alpha_v,\qquad
 (DB^2)_{uv}=\alpha_u.
\]
Moreover \((BDB)_{uv}=\alpha_z\), because \(z\) is the
unique common neighbour and the terms indexed by \(u,v\)
vanish.  This proves \eqref{eq:polarity-edge-count}.

If $z$ is absolute, both endpoints are nonabsolute.
Thus the sum of the three indicators is at most two, and
\eqref{eq:polarity-edge-count} is at least $q-1$.

Suppose first that $p=z$ and $p$ is nonabsolute.
The paths using $p$ as the first internal vertex number
$|N_P(p)\cap N_P(v)|=1-\alpha_v$, and those using it as the
second internal vertex number $1-\alpha_u$, by
\eqref{eq:polarity-codegrees}.  These two path families are
disjoint.  Deleting $p$ therefore removes exactly
$2-\alpha_u-\alpha_v$ paths and leaves exactly $q-1$.
If $p=z$ is absolute, the two corresponding codegrees are zero,
so the deletion removes no path and leaves $q$.

If $p\ne z$, it is adjacent to at most one of $u,v$.
If it is adjacent to neither, it occurs in no such path.
If it is adjacent to exactly one, the codegree bound shows
that it occurs in at most one path.  Thus at most one path
is lost, proving \eqref{sharp:arbitrary-puncture-price}.
When $p$ is absolute, the only case in which the original
count is $q-1$ has both endpoints absolute; independence
of the absolute points then means no path is lost.
In all other cases the original count is at least $q$.
This proves the stronger bound for an absolute deletion.

Finally, two distinct length-three $u$--$v$ paths in a
$C_4$-free graph cannot share their first or last edge:
such a shared edge would give two common neighbours to
another pair.  If their middle edge is shared, they either
coincide or traverse it in opposite directions; the latter
possibility also gives a four-cycle.  An end edge of one
path cannot be an end edge of the other at the opposite
endpoint, or its middle edge, because $u,v$ do not occur
internally.  Thus the three-edge sets of these paths are
pairwise disjoint.  Deleting $p$ preserves this property.
\end{proof}

The identity \eqref{eq:polarity-edge-count} is the standard
single-edge count for polarity graphs; compare
\cite[Lemma~2.5]{HeMaYang2023}.
The point-deletion bounds are used in the construction below and
in Section~\ref{sec:applications}.

\begin{proposition}[An attaining construction]
\label{prop:upper-construction}
For every power of two \(q\ge4\), there is a graph \(G\)
on \(q^2+q\) vertices with \(m_0+1\) edges and exactly
\(q-1\) four-cycles.  It has an edge \(e\) such that
\(F=G-e\) satisfies \eqref{eq:core-hypotheses} and
\(\eta(F)=0\).
\end{proposition}

\begin{proof}
Take the points of \(\mathrm{PG}(2,q)\) as vertices,
and join distinct projective points \(x,y\) when
\[
 x_0y_0+x_1y_1+x_2y_2=0.
\]
The nondegenerate symmetric bilinear form defines a
polarity.  In characteristic two its absolute points
form the line
\[
 \mathcal A=\{[x_0:x_1:x_2]:x_0+x_1+x_2=0\}.
\]
There are \(q+1\) absolute points, each of degree \(q\);
the other \(q^2\) points have degree \(q+1\).
The resulting graph \(H_q\) is \(C_4\)-free and has
\[
 e(H_q)=\frac{(q+1)q+q^2(q+1)}2=M.
\]
The point \(c=[1:1:1]\) is not absolute and has
neighbourhood \(\mathcal A\).

Choose distinct \(p,u,v\in\mathcal A\), delete \(p\),
and add the edge \(uv\).  This gives \(n=N-1\) vertices
and \(M-q+1=m_0+1\) edges.
The pair \(u,v\) has common neighbour \(c\).
Equation~\eqref{eq:polarity-edge-count} gives \(q-1\)
four-cycles before deleting \(p\).  Since \(p\) is
adjacent to neither \(u\) nor \(v\), the deletion
does not change this count.

It remains to verify the surplus assertion.
Put \(X=\mathcal A\setminus\{p\}\) and \(Y=N_{H_q}(p)\).
These sets are disjoint and both have size \(q\).
In \(F=H_q-p\), precisely the vertices of \(X\cup Y\)
have degree \(q\); all other vertices have degree \(q+1\).
Every full-degree vertex \(w\) differs from \(c\), because
\(c\in Y\).  It therefore has exactly one absolute
neighbour, since its polar line meets \(\mathcal A\)
in one point.  This neighbour belongs to \(X\), as
\(w\notin N_{H_q}(p)\).  Also \(p,w\) have a unique
common neighbour, which belongs to \(Y\).
Thus \(w\) has exactly two neighbours of deficit one,
and all its other neighbours have deficit zero.
Therefore \(\eta(F)=0\).
\end{proof}

\begin{proof}[Proof of Corollary~\ref{cor:order-of-magnitude}]
For \(q=2^k\), the theorem of Firke, Kosek, Nash, and
Williford \cite{FirkeEtAl2013} gives
\(\ex(q^2+q,C_4)=m_0\).
The lower bound follows from Theorem~\ref{thm:main}
and the integrality of the number of four-cycles.
Proposition~\ref{prop:upper-construction} gives the upper
bound.  Since \(q\sim\sqrt{q^2+q}\), the stated
order of magnitude follows.
\end{proof}

\subsection{Elementary geometric bounds}
\label{sec:geometric-bounds}

\begin{lemma}[Concurrency from a bounded exceptional set]
\label{struct:bounded-pencil}
Let $\mathcal F$ be a family of $r$ distinct lines of a projective
plane. Suppose that the intersection point of every two distinct
lines of $\mathcal F$ belongs to a set $B$, and every line of
$\mathcal F$ has at most $a$ points in
$B$.  If $r-1>a(a-1)$, all lines of $\mathcal F$ are concurrent.
\end{lemma}

\begin{proof}
If the family is not concurrent, fix $\ell\in\mathcal F$.
For every point $p\in\ell\cap B$ used as an intersection,
there is a line $\ell'\in\mathcal F$ not through $p$.
All members of $\mathcal F$ through $p$ meet $\ell'$ in
distinct points of $B$, so at most $a$ of them exist, including
$\ell$.  Partitioning $\mathcal F\setminus\{\ell\}$ by its
intersection with $\ell$ gives $r-1\le a(a-1)$.
\end{proof}

\begin{lemma}[An elementary edge bound for even-order polarities]
\label{struct:even-polarity-bound}
Let $\pi$ be a polarity of a projective plane of even order $q$.
Its loopless graph $P_\pi$ has minimum degree at least $q$ and
at most $M$ edges.  If it has $M$ edges, its absolute points form
a line of $q+1$ points.
\end{lemma}

\begin{proof}
An absolute point has degree $q$ and any other point has degree
$q+1$.  Distinct absolute points cannot be adjacent: otherwise
their two distinct polar lines both contain both points.
For a nonabsolute vertex $x$, a neighbour $y$ is isolated in the
matching induced by $N(x)$ precisely when $y$ is absolute.
Indeed, the distinct lines $\pi(x),\pi(y)$ meet at a unique point;
this supplies a common neighbour unless that point is $y$ itself,
which is exactly the absolute case.  Since $q+1$ is odd, $x$ has
an odd, positive number of absolute neighbours.

If $a$ is the number of absolute points, counting their edges to
the $N-a$ other points gives $qa\ge N-a$ and thus $a\ge q+1$.
Consequently
\[
 e(P_\pi)=\frac{N(q+1)-a}{2}\le M.
\]
If equality holds, $a=q+1$.
Every line meets the absolute set: an absolute point's polar line
contains that point, and every other polar line contains the positive
odd number of absolute neighbours just proved.
A blocking set of $q+1$ points is a line.  To see this, take a line
through two of its points.  If that line contained a point outside
the set, the other $q$ lines through that outside point would require
at least $q$ additional points of the set off the chosen line,
whereas at most $q-1$ are available.  Hence the chosen line consists
entirely of the $q+1$ absolute points.
\end{proof}

% Source: sections/supersaturation.tex
\section{Supersaturation one edge above the bound}
\label{sec:supersaturation}

We prove Theorem~\ref{thm:main} by treating all possible degree
configurations at $m_+=m_0+1$ edges. Throughout this section,
$Q=\Nfour(G)$. The estimates are summarized below; the final
subsection combines them and passes to larger edge counts.

\begin{center}
\begin{tabular}{@{}p{0.65\linewidth}l@{}}
\toprule
Degree configuration & Lower bound\\
\midrule
$\Delta(G)\le q+1$ & $12Q\ge q+5$\\
$\Delta(G)\ge q+3$ & $Q>q/2$\\
Exactly one vertex of degree $q+2$, all others at most $q+1$
 & $12Q\ge q-1$\\
At least two vertices of degree $q+2$, maximum degree $q+2$
 & $Q>q/12$\\
\bottomrule
\end{tabular}
\end{center}
All four estimates hold for even $q\ge1600$; the individual
statements below give their respective ranges. In the last case,
we also prove the asymptotic improvement $Q>q/4-3q^{3/4}$.

\subsection{Maximum degree at most \texorpdfstring{$q+1$}{q+1}}
\label{sec:capped}

\begin{theorem}
\label{thm:capped}
Let $q\ge2$ be even.  If $G$ has $q^2+q$ vertices, $m_+$ edges,
and maximum degree at most $q+1$, then
\begin{equation}
 12\Nfour(G)\ge q+5.
 \label{eq:capped-bound}
\end{equation}
\end{theorem}

\begin{proof}
In this proof $V(G)=L\cup H$.  Write $h=|H|$, and put
\begin{align*}
 \sigma&=\sum_{v\in L}(\delta_v-1),
 &\chi&=\sum_{v\in L}\delta_v(\delta_v-1),\\
 \omega&=\sum_{uv\in E(G[L])}(\delta_u+\delta_v),
 &\beta&=\sum_{v\in H}\varepsilon_v,\\
 \mathcal D&=4+2\sigma+\chi+\omega.
\end{align*}
All these parameters are nonnegative.  The degree sum gives
\begin{equation}
 |L|=2q-2-\sigma,
 \qquad h=q^2-q+2+\sigma.
 \label{eq:capped-part-sizes}
\end{equation}
Let $B=H\setminus Z_0$ and $b=|B|$.
Weighted counting of the edges between $L$ and $H$ gives
\[
 \sum_{v\in H}a_v
 =\sum_{w\in L}\delta_w d_H(w)
 =q(2q-2)-\chi-\omega.
\]
Indeed, $d_H(w)=q+1-\delta_w-d_L(w)$,
$\sum_{w\in L}\delta_w^2=\chi+2q-2$, and
$\sum_{w\in L}\delta_w d_L(w)=\omega$.
Consequently
\begin{equation}
 \mathcal D=\sum_{v\in H}(2-a_v),
 \qquad
 \sum_{v\in B}u_v=b-\mathcal D+\beta.
 \label{eq:capped-bad-mass}
\end{equation}
For the second identity, sum $u_v=a_v-1+\varepsilon_v$ over $H$
and subtract the contribution of the $h-b$ good vertices.

We shall use two bounds for $b$.  Let
\[
 C=\{v\in H:\varepsilon_v>0\},\qquad
 T=\{v\in H:\varepsilon_v=0,\ a_v\ge3\},\qquad
 p=\sum_{v\in T}(a_v-2).
\]
By Lemma~\ref{lem:good-vertices}, $B=C\cup T$ is a disjoint union.
Since $|C|\le\beta$, $|T|\le p$, and
\[
 \mathcal D=2|C|-\sum_{v\in C}a_v-p,
\]
we have
\begin{equation}
 b\le3|C|-\sum_{v\in C}a_v-\mathcal D
 \le3\beta-\mathcal D.
 \label{eq:capped-bad-bound}
\end{equation}
All $a_v$ are nonnegative under the degree hypothesis.  Thus, for
each $w\in C$,
\begin{equation}
 b+a_w\le3\beta-\mathcal D.
 \label{eq:capped-marked-bound}
\end{equation}

\paragraph{A vertex of $B$ with at most one uncovered partner.}
Suppose that $v\in B$ and $u_v\le1$.
Then $v\in C$, since $\varepsilon_v=0$ would imply
$a_v=u_v+1\le2$ and hence $v\in Z_0$.
Choose $w$ such that $R_{vw}>0$.
For every good vertex $x$, equation \eqref{eq:codegree-commutator}
has the form
\begin{equation}
 A_{v,f(x)}+\sum_y R_{vy}A_{yx}
 =\sum_{z:U_{vz}=1}A_{zx}.
 \label{eq:capped-small-row}
\end{equation}
If $u_v=0$, this forces $w$ to have no good neighbour.
If $u_v=1$, let $z$ be the unique uncovered partner of $v$.
Every good neighbour of $w$ is also adjacent to $z$.
The vertices $w,z$ are distinct because $R_{vw}>0$ and $U_{vz}=1$.
Two such neighbours would form a four-cycle with $w,z$,
contradicting Lemma~\ref{lem:good-vertices}.
In either case,
\begin{equation}
 d_{Z_0}(w)\le1.
 \label{eq:capped-w-good}
\end{equation}

If $w\in H$, symmetry of $R$ gives $w\in C$.
The vertex $w$ has at most $b-1$ neighbours in $B$ and at most
$a_w$ neighbours in $L$.  Equations \eqref{eq:capped-marked-bound}
and \eqref{eq:excess-budget} give
\[
 q+1=d(w)\le1+(b-1)+a_w
 \le3\beta-\mathcal D\le12Q-4.
\]
This proves \eqref{eq:capped-bound}.

If $w\in L$, put $\delta=\delta_w\ge1$ and $s=d_L(w)$.
The contributions of $w$ to $\sigma,\chi$, and of the edges of
$G[L]$ incident with $w$ to $\omega$, give
\[
 \mathcal D\ge
 4+2(\delta-1)+\delta(\delta-1)+(\delta+1)s.
\]
In particular,
\begin{equation}
 \mathcal D-\delta-s\ge\delta^2+2+\delta s\ge3.
 \label{eq:capped-low-cost}
\end{equation}
Using \eqref{eq:capped-w-good} and \eqref{eq:capped-bad-bound},
we obtain
\[
 q+1=d(w)+\delta
 \le1+b+s+\delta
 \le1+3\beta-\mathcal D+s+\delta
 \le3\beta-2.
\]
Here $\varepsilon_w\ge1$ and $w\notin H$, so
$\beta\le4Q-1$.  Thus $q+1\le12Q-5$, again implying
\eqref{eq:capped-bound}.

\paragraph{Every vertex of $B$ has at least two uncovered partners.}
We may now assume that $u_v\ge2$ for all $v\in B$.
Equation \eqref{eq:capped-bad-mass} yields
\begin{equation}
 b\le\beta-\mathcal D.
 \label{eq:capped-two-uncovered}
\end{equation}
Suppose first that $u,w$ are good and $f(u)=w$.
Lemma~\ref{lem:good-vertices} shows that $w$ is the only good
neighbour of $u$.  Since $a_u=2$, at most two neighbours of $u$
belong to $L$.  Hence $b\ge q-2$, and
\[
 q-2\le b\le\beta-\mathcal D\le4Q-4.
\]
The resulting bound $4Q\ge q+2$ is stronger than
\eqref{eq:capped-bound}.

It remains to consider the case where no two good vertices are
uncovered.  Put
\[
 Z=\{v\in Z_0:f(v)\in L\}.
\]
Every good vertex outside $Z$ has its uncovered partner in $B$.
Therefore, by \eqref{eq:capped-bad-mass} and
\eqref{eq:capped-two-uncovered},
\begin{align}
 |Z|&\ge h-b-\sum_{v\in B}u_v
      =h-2b+\mathcal D-\beta\notag\\
     &\ge h-3\beta+3\mathcal D.
 \label{eq:capped-fibre-lower}
\end{align}

Let $X=f(Z)\subseteq L$ and $Y=L\setminus X$.
For distinct $a,b\in X$, choose $u,v\in Z$ with $f(u)=a$ and
$f(v)=b$.  If $u$ were adjacent to $b$, then
\eqref{eq:good-commutator} would make $v$ adjacent to $a$,
producing the four-cycle $a,u,b,v,a$.
Thus each $u\in Z$ has exactly one neighbour in $X$, namely $f(u)$.

Because $a_u=2$, every $a\in X$ has deficit one or two.
If $\delta_{f(u)}=1$, then $u$ has precisely one other neighbour
$b\in L$, which lies in $Y$ and has deficit one.
For each pair $(a,b)\in X\times Y$, at most one such vertex $u$
is possible, since two would form a four-cycle with $a,b$.
If $\delta_{f(u)}=2$, there is no other neighbour of $u$ in $L$,
and the fibre $f^{-1}(f(u))\cap Z$ has size at most
$d(f(u))=q-1$.
Write
\[
 x_i=|\{a\in X:\delta_a=i\}|\quad(i=1,2),\qquad
 y_1=|\{b\in Y:\delta_b=1\}|.
\]
Then
\[
 |Z|\le x_1y_1+(q-1)x_2,
 \qquad x_1+y_1+2x_2\le2q-2.
\]
Since $0\le x_2\le q-1$, it follows that
\begin{align}
 |Z|&\le(q-1-x_2)^2+(q-1)x_2\notag\\
     &=(q-1)^2-x_2(q-1-x_2)\le(q-1)^2.
 \label{eq:capped-fibre-upper}
\end{align}
Combining \eqref{eq:capped-fibre-lower},
\eqref{eq:capped-fibre-upper}, and \eqref{eq:capped-part-sizes}
gives
\[
 3\beta\ge h+3\mathcal D-(q-1)^2
 =q+13+7\sigma+3\chi+3\omega.
\]
As $\beta\le4Q$, this proves $12Q\ge q+13$ and completes the
proof.
\end{proof}

\subsection{Vertices of degree at least \texorpdfstring{$q+3$}{q+3}}
\label{sec:large-degree}

We use the following form of the neighbourhood-complement argument
of Firke et al.~\cite[Lemma~1]{FirkeEtAl2013}.

\begin{lemma}
\label{lem:neighbourhood-complement}
Let $G$ be a graph on $\nu\ge3$ vertices with $m$ edges and
$Q$ four-cycles.  If a vertex $u$ has degree $D$, put
\[
 s=2m-D-(\nu-1)-Q.
\]
If $s/(\nu-1)\ge1/2$, then
\begin{equation}
 (\nu-1)\binom{s/(\nu-1)}2
 \le\binom{\nu-D}{2}+2Q.
 \label{eq:neighbourhood-complement}
\end{equation}
Here $\binom{x}{2}=x(x-1)/2$ for real $x$.
\end{lemma}

\begin{proof}
Set $S=N(u)$ and $B=V(G)\setminus S$.
For $v\ne u$, put
\[
 p_v=|N(v)\cap S|=c_{uv},\qquad
 b_v=|N(v)\cap B|=d(v)-p_v.
\]
Counting four-cycles containing $u$ gives
$\sum_{v\ne u}\binom{p_v}{2}=Q_u\le Q$.
Consequently
\[
 \sum_{v\ne u}p_v
 \le(\nu-1)+\sum_{v\ne u}(p_v-1)_+
 \le(\nu-1)+Q,
\]
and $\sum_{v\ne u}b_v\ge s$.

Since $N(u)\cap B=\varnothing$, the number of two-edge paths
with endpoints in $B$ is
\[
 \sum_{v\ne u}\binom{b_v}{2}
 =\sum_{\{x,y\}\subseteq B}c_{xy}.
\]
It is at most
\begin{align*}
 \binom{|B|}{2}
 +\sum_{\{x,y\}\subseteq B}(c_{xy}-1)_+
 &\le\binom{|B|}{2}
 +\sum_{\{x,y\}\subseteq V(G)}\binom{c_{xy}}2\\
 &=\binom{\nu-D}{2}+2Q.
\end{align*}
Jensen's inequality, together with the monotonicity of
$x(x-1)/2$ on $[1/2,\infty)$, bounds the same number below by
$(\nu-1)\binom{s/(\nu-1)}2$.
\end{proof}

\begin{theorem}
\label{thm:large-degree}
Let $q\ge8$ be an integer.  If $G$ has $q^2+q$ vertices,
at least $m_+$ edges, and maximum degree at least $q+3$, then
\[
 \Nfour(G)>q/2.
\]
\end{theorem}

\begin{proof}
Suppose that $Q\le q/2$, and choose a vertex of degree
$D\ge q+3$.  Put $a=n-1=q^2+q-1$.
For $D\le n-1$ and $e(G)\ge m_+$, the quantity $s$ in
Lemma~\ref{lem:neighbourhood-complement} satisfies
\[
 s\ge2m_+-2(n-1)-Q=q^3-3q+4-Q.
\]
Moreover,
\[
 q^3-3q+4-Q-(q-2)a=q^2+2-Q>0.
\]
Thus $s/a>q-2\ge6$, and
Lemma~\ref{lem:neighbourhood-complement} implies
\begin{equation}
 F(D,Q):=
 a\binom{(2m_+-D-a-Q)/a}{2}
 -\binom{n-D}{2}-2Q\le0.
 \label{eq:large-degree-F}
\end{equation}
The replacement of $e(G)$ by $m_+$ is valid by the same
monotonicity.

For fixed $Q$, the coefficient of $D^2$ in $F(D,Q)$ is
$1/(2a)-1/2<0$.  Its minimum on $[q+3,n-1]$ is therefore
attained at an endpoint.  Expanding at the first endpoint gives
\begin{equation}
 2F(q+3,Q)
 =q^2+3q-12-(2q+3)Q+\frac{(2q+Q)^2}{a}.
 \label{eq:large-degree-endpoint}
\end{equation}
The polynomial part is at least $3q/2-12\ge0$, and the last
term is positive.  Hence $F(q+3,Q)>0$.
At the other endpoint,
\[
 F(n-1,Q)
 \ge a\binom{q-2}{2}-2Q
 \ge a\binom{q-2}{2}-q>0.
\]
This contradicts \eqref{eq:large-degree-F}.
\end{proof}


\subsection{A unique vertex of degree \texorpdfstring{$q+2$}{q+2}}
\label{sup:one-high-section}

The remaining degree configurations have maximum degree $q+2$.
We first consider graphs with a unique vertex of this degree.

\begin{theorem}
\label{sup:one-high}
Let $q\ge6$ be even.  Suppose that $G$ has $n$ vertices and $m_+$
edges, exactly one vertex of degree $q+2$, and all other degrees at
most $q+1$.  Then
\[
 12\Nfour(G)\ge q-1.
\]
\end{theorem}

Throughout the proof, $z$ denotes the unique vertex of degree
$q+2$, so $\delta_z=-1$.
We use the notation, codegree identities, and good-vertex
properties from Section~\ref{sec:counting}.
In addition to \eqref{eq:excess-budget}, every pair of distinct
vertices satisfies
\begin{equation}
 \binom{c_{uv}}2\le Q,
 \label{sup:pair-cycle-budget}
\end{equation}
because the cycles counted on the left have $u,v$ as opposite
vertices.

\subsubsection{Signed mass and short uncovered rows}

Put $h=|H|$.
Define
\begin{align*}
 \sigma&=\sum_{v\in L}(\delta_v-1),
 &\chi&=\sum_{v\in L}\delta_v(\delta_v-1),\\
 \omega&=\sum_{uv\in E(G[L])}(\delta_u+\delta_v),
 &\tau&=\sum_{v\in N(z)\cap L}(\delta_v-1),\\
 \beta&=\sum_{v\in H}\varepsilon_v,
 &k&=d_H(z),\qquad
 \mathcal D=2+2\sigma+\chi+\omega+\tau.
\end{align*}
Write $B=H\setminus Z_0$ and $b=|B|$.
The degree sum and the local deficit identity give
\begin{align}
 \sum_{v\in L}\delta_v&=2q-1,
 & |L|&=2q-1-\sigma,
 & h&=q(q-1)+\sigma,
 \label{sup:parts}\\
 k&\le1+\tau+\varepsilon_z,
 &\beta+\varepsilon_z&\le4Q,
 \label{sup:high-budget}\\
 \mathcal D&=\sum_{v\in H}(2-a_v),
 &\sum_{v\in B}u_v&=b-\mathcal D+\beta.
 \label{sup:bad-mass}
\end{align}
For the first relation in \eqref{sup:high-budget}, use
$a_z=q+2-k+\tau$ in \eqref{eq:local-deficit}.
For \eqref{sup:bad-mass}, weighted edge counting gives
\[
 \sum_{v\in H}a_v
 =\sum_{w\in L}\delta_wd_H(w)-k
 =q(2q-1)-\chi-\omega-a_z-k
 =2q^2-2q-2-\chi-\omega-\tau.
\]
Summation of \eqref{eq:local-deficit} over $B$ gives the other identity.

Let $C=\{v\in H:\varepsilon_v>0\}$ and
\[
 D_- =\sum_{v\in H}(2-a_v)_+,
 \qquad D_+ =\sum_{v\in H}(a_v-2)_+.
\]
If $a_v<2$, then $\varepsilon_v\ge1$ and
$2-a_v\le1+\varepsilon_v\le2\varepsilon_v$.
Thus $D_-\le2\beta$ and $D_+\le2\beta-\mathcal D$.
Vertices of $B\setminus C$ have $a_v\ge3$, and consequently
\begin{equation}
 b\le3\beta-\mathcal D,
 \qquad b+a_w\le3\beta-\mathcal D+2\quad(w\in C).
 \label{sup:marked-bound}
\end{equation}
To obtain the second inequality without assuming $a_v\ge0$, observe
that
\[
 b\le |C|+D_+-\sum_{v\in C}(a_v-2)_+.
\]
For $w\in C$, the quantity $a_w-(a_w-2)_+$ is at most two.

\begin{lemma}
\label{sup:outside-witness}
If there exist $v\in B$ and $w\ne z$ such that $u_v\le1$ and
$R_{vw}>0$, then $12Q\ge q-1$.
\end{lemma}

\begin{proof}
The vertex $v$ belongs to $C$.
For every good $x$, equation \eqref{eq:codegree-commutator} becomes
\begin{equation}
 A_{v,f(x)}+\sum_yR_{vy}A_{yx}
 =\sum_{a:U_{va}=1}A_{ax}.
 \label{sup:short-row}
\end{equation}
If $u_v=0$, then $w$ has no good neighbour.
If $u_v=1$, all good neighbours of $w$ are also adjacent to the
unique uncovered partner of $v$.  That partner differs from $w$,
and two such neighbours would give a four-cycle containing good
vertices.  In all cases, $d_{Z_0}(w)\le1$.

If $w\in H$, then $w\in C$.
Writing $t=A_{wz}$, we have $d_L(w)\le a_w+t$ and hence
\[
 q+1=d(w)\le1+(b-1)+a_w+2t
 \le b+a_w+2\le3\beta-\mathcal D+4\le12Q+2.
\]
This gives the assertion.
If $w\in L$, put $\delta=\delta_w$, $s=d_L(w)$, and $t=A_{wz}$.
The contributions of $w$ and its incident low edges imply
\[
 \mathcal D\ge2+2(\delta-1)+\delta(\delta-1)
                 +(\delta+1)s+(\delta-1)t.
\]
Thus
$\mathcal D-\delta-s-t\ge\delta^2+\delta s+(\delta-2)t\ge0$.
It follows that
\[
 q+1=d(w)+\delta\le1+b+s+t+\delta\le1+3\beta.
\]
Since $\varepsilon_w\ge1$ and $w\notin H$,
$\beta\le4Q-1$.  Therefore $12Q\ge q+3$ in this case.
\end{proof}

\paragraph{Zero-row pairing.}
The remaining short rows have their excess entirely at $z$.
The extra capacity furnished by these rows is controlled by a
pairing inside $N(z)\cap H$.

\begin{lemma}
\label{sup:zero-row-pairing}
Suppose that every $v\in B$ with $u_v\le1$ has
$R_{vw}=0$ for all $w\ne z$.
Put
\[
 S=\{v\in B:u_v\le1\},\qquad
 S_0=\{v\in B:u_v=0\},\qquad s_0=|S_0|,
 \qquad \lambda=\sum_{v\in S}(2-u_v).
\]
Then
\begin{equation}
 \lambda\le\varepsilon_z+s_0,\qquad
 2s_0\le k,\qquad
 2s_0+g\le k,
 \quad g=|N(z)\cap Z_0|.
 \label{sup:zero-row-budget}
\end{equation}
Moreover, every $v\in S_0$ is adjacent to $z$, has
$\varepsilon_v=1$ and $a_v=0$, and has exactly one low neighbour,
of deficit one.
\end{lemma}

\begin{proof}
Every member of $S$ has positive excess, so
$\varepsilon_v=R_{vz}\ge1$ for $v\in S$.
By symmetry of $R$, $\sum_{v\in S}\varepsilon_v\le\varepsilon_z$.
Writing $s_1=|S\setminus S_0|$ gives
$\lambda=2s_0+s_1\le\varepsilon_z+s_0$.

Let $v\in S_0$.
If $v$ were not adjacent to $z$, every vertex of $N(v)$ would
have codegree one with $v$, contrary to the odd order $q+1$ of
this neighbourhood.  Hence $vz$ is an edge.
Equation \eqref{eq:local-deficit} gives $a_v=1-\varepsilon_v$.
Since $a_v\ge-1$, we have $1\le\varepsilon_v\le2$.
Also
\[
 2e(G[N(v)])=\sum_{w\in N(v)}c_{vw}=q+1+\varepsilon_v,
\]
so $\varepsilon_v$ is odd.  Thus $\varepsilon_v=1$ and $a_v=0$.
The positive neighbour deficits of $v$ sum to one, since the
neighbour $z$ contributes $-1$.  This proves the assertion about
its low neighbour.  In particular $c_{vz}=2$.

For every $w\in N(v)\setminus\{z\}$, one has $c_{zw}=1$.
The vertex $v$ is a common neighbour of $z,w$; another common
neighbour $x$ would make $z,w$ two distinct common neighbours of
$v,x$, contradicting the support condition on the $v$th row of
$R$.
The two common neighbours of $v,z$ cannot both be low, because
$v$ has only one low neighbour.  At least one therefore belongs
to $N(z)\cap H$, and it does not belong to $S_0$, since its
codegree with $z$ is one.
These choices are distinct for distinct members of $S_0$:
two members of $S_0$ already have common neighbour $z$, and
their mutual codegree is exactly one.
We have obtained an injection from $S_0$ into
$(N(z)\cap H)\setminus S_0$, proving $2s_0\le k$.

If $S_0$ is nonempty, apply \eqref{sup:short-row} to one of its
members.  The right-hand side is zero, and $R_{vz}=1$, so
$A_{zx}=0$ for every good $x$; that is, $g=0$.
If $S_0$ is empty, $g\le k$ is immediate.
These two cases prove $2s_0+g\le k$.
\end{proof}

\subsubsection{The fibre deficit and the neighbourhood union}

\begin{proof}[Proof of Theorem~\ref{sup:one-high}]
Suppose, for a contradiction, that $12Q<q-1$.
Lemma~\ref{sup:outside-witness} shows that the hypotheses of
Lemma~\ref{sup:zero-row-pairing} hold.
From \eqref{sup:bad-mass},
\[
 2b-\lambda\le\sum_{v\in B}u_v=b-\mathcal D+\beta,
 \qquad b\le\beta-\mathcal D+\lambda.
\]
If good vertices $u,v$ are uncovered, they are adjacent and have
no other good neighbours.  A good vertex $x$ has at most
$2+A_{xz}$ low neighbours and at most $A_{xz}$ high neighbours.
Since $c_{uv}=0$, at most one of $u,v$ is adjacent to $z$;
also their bad-neighbour sets are disjoint.
Consequently $b\ge2q-6$.
On the other hand, $s_0\le\varepsilon_z$, so
\[
 b\le\beta+2\varepsilon_z-\mathcal D\le5Q-2.
\]
Thus $5Q\ge2q-4$, contradicting $12Q<q-1$ for $q\ge6$.
There is therefore no uncovered pair of good vertices.

\paragraph{Exceptional full-degree vertices.}
Set
\[
 Z=\{v\in Z_0:f(v)\in L,\ vz\notin E(G)\},
 \qquad \mu=h-|Z|.
\]
Every good vertex omitted from $Z$ either has its uncovered
partner in $B$ or is adjacent to $z$.
Using \eqref{sup:bad-mass} and \eqref{sup:zero-row-budget}, we obtain
\begin{align}
 \mu&\le b+\sum_{v\in B}u_v+g
      =2b-\mathcal D+\beta+g\notag\\
     &\le3\beta-3\mathcal D+2\lambda+g\notag\\
     &\le3\beta+2\varepsilon_z+k-3\mathcal D\notag\\
     &\le12Q-5-6\sigma-3\chi-3\omega-2\tau.
 \label{sup:improved-fibre-deficit}
\end{align}

Put $X=f(Z)$ and $Y=L\setminus X$.
Every $u\in Z$ has exactly one neighbour in $X$, namely $f(u)$:
another such neighbour, together with \eqref{eq:good-commutator},
would give a four-cycle containing good vertices.
Since $u$ is not adjacent to $z$, its positive neighbour deficits
sum to two.
If $\delta_{f(u)}=1$, it has one further low neighbour, of deficit
one, in $Y$, and no two such vertices use the same pair in
$X\times Y$.
If $\delta_{f(u)}=2$, its fibre has size at most $q-1$.
With
\[
 x_i=|\{a\in X:\delta_a=i\}|\ (i=1,2),
 \qquad y_1=|\{b\in Y:\delta_b=1\}|,
\]
it follows that
\begin{equation}
 |Z|\le x_1y_1+(q-1)x_2,
 \qquad x_1+y_1+2x_2\le2q-1.
 \label{sup:fibre-capacity}
\end{equation}
If $\sigma\ge1$ and $x_2\ge1$, the right-hand side is at most
\[
 (q-x_2)(q-1-x_2)+(q-1)x_2
 =q(q-1)-x_2(q-x_2)\le q(q-1)-(q-1).
\]
If $\sigma\ge1$ and $x_2=0$, an inactive vertex of deficit at
least two gives $x_1+y_1\le2q-3$, and the same upper bound holds.
Since $h=q(q-1)+\sigma$, either case yields $\mu\ge q-1+\sigma$,
contrary to \eqref{sup:improved-fibre-deficit} and $12Q<q-1$.
Thus $\sigma=0$.

All low deficits are now one, $|L|=2q-1$, $h=q(q-1)$,
$\chi=\tau=0$, and $\mathcal D=2+\omega\ge2$.
The vertices of $Z$ give distinct edges of a simple bipartite
support graph on $X,Y$, whose maximum degree is at most $q$.
If one part had size at most $q-2$, then
$|Z|\le q(q-2)=h-q$, contradicting
\eqref{sup:improved-fibre-deficit}.
Consequently
\begin{equation}
 \{|X|,|Y|\}=\{q,q-1\},\qquad
 \mu\le3\beta+2\varepsilon_z+k-3\mathcal D
      \le12Q-5<q.
 \label{sup:balanced-support}
\end{equation}
Here $\mu$ is also the number of missing support pairs.
Since $\tau=0$, \eqref{sup:high-budget} gives
$k\le1+\varepsilon_z\le1+Q$.

Let $r=|N(z)\cap X|$, $s=|N(z)\cap Y|$, and
$\ell=r+s=q+2-k$.
Every pair in $(N(z)\cap X)\times(N(z)\cap Y)$ is missing
from the support graph, so $rs\le\mu$.
If $k\le1$, then $\ell\ge q+1$, both $r,s$ are positive, and
$rs\ge\ell-1\ge q$, a contradiction.
Thus $k\ge2$.
If $r,s\ge2$, then
\[
 rs\ge2\ell-4=2q-2k\ge2q-2-2Q>\frac{11}{6}(q-1)\ge q,
\]
again a contradiction.  Thus $\min(r,s)\le1$.

For every $w\in N(z)\cap H$, the support pairs belonging to
$N(w)\cap Z$ form a matching, and neither coordinate of such
a pair lies in $N(z)\cap L$.  The first assertion follows from
the absence of four-cycles through good vertices; the second
follows by considering the cycle $z,w,u,a,z$ for
$u\in N(w)\cap Z$ and a low neighbour $a$ of $u$.
Since $\min(r,s)\le1$,
one of $r,s$ is at least $q+1-k$, while its support part has at
most $q$ vertices. Hence
\begin{equation}
 d_Z(w)\le\min\{|X\setminus N(z)|,|Y\setminus N(z)|\}
 \le k-1.
 \label{sup:w-support-bound}
\end{equation}

Suppose that $k\ge3$, and choose distinct $w_1,w_2,w_3$ in
$N(z)\cap H$.
Put $A_i=N(w_i)\setminus\{z\}$, so $|A_i|=q$.
Each common point of $A_i,A_j$ gives a distinct four-cycle
$z,w_i,x,w_j,z$.  Thus
\[
 \sum_{i<j}|A_i\cap A_j|\le Q,
 \qquad \left|\bigcup_{i=1}^3A_i\right|\ge3q-Q.
\]
The union contains at most $3(k-1)$ points of $Z$,
at most $\sum_{i=1}^3c_{zw_i}\le3+\varepsilon_z$ points of
$N(z)\cap L$, at most $|L\setminus N(z)|=q-3+k$ other low
points, and at most $\mu$ full-degree points outside $Z$.
Therefore
\[
 \mu\ge2q+3-4k-\varepsilon_z-Q.
\]
Combining this with \eqref{sup:balanced-support} gives
\[
 2q+3+3\mathcal D
 \le3\beta+3\varepsilon_z+5k+Q
 \le18Q+5.
\]
Hence $18Q\ge2q+4$, contrary to $12Q<q-1$.
We conclude that $k=2$.

\paragraph{Joint-codegree cancellation.}
Write $N(z)\cap H=\{u,v\}$.
The union of $N(u)\setminus\{z\}$ and $N(v)\setminus\{z\}$
has size $2q+1-c_{uv}$. By \eqref{sup:w-support-bound}, it
contains at most two vertices of $Z$, at most $c_{zu}+c_{zv}$
vertices of $N(z)\cap L$, at most $q-1$ vertices of
$L\setminus N(z)$, and at most $\mu$ full-degree vertices outside
$Z$. Comparing these counts gives
\begin{equation}
 \mu\ge q-c_{zu}-c_{zv}-c_{uv}.
 \label{sup:two-neighbourhoods}
\end{equation}
To bound the three codegrees together, note that $z$ is a common
neighbour of $u,v$.
Every other common neighbour $x$ differs from $u,v,z$ and has
$c_{zx}\ge2$.
These contributions occupy different positions of the $z$th
row of $R$ from those indexed by $u,v$, and consequently
\[
 (c_{zu}-1)_++(c_{zv}-1)_++c_{uv}-1\le\varepsilon_z.
\]
Thus $c_{zu}+c_{zv}+c_{uv}\le3+\varepsilon_z$.
Equation \eqref{sup:two-neighbourhoods} gives
$\mu\ge q-3-\varepsilon_z$.
On the other hand, \eqref{sup:balanced-support}, $k=2$, and
$\mathcal D\ge2$ imply
\[
 \mu\le3\beta+2\varepsilon_z-4
      \le12Q-\varepsilon_z-4.
\]
The excess at $z$ cancels, giving $12Q\ge q+1$.
This is the final contradiction.
\end{proof}

\subsection{Several vertices of degree \texorpdfstring{$q+2$}{q+2}}
\label{sup:multiple-section}

In this section $G$ has $n$ vertices and $m_+$ edges, and
$\Delta(G)\le q+2$.
Let $T=\{v:d(v)=q+2\}$, $t=|T|$, and
\[
 \alpha=\sum_{v\in L}\delta_v^2.
\]
The improvement uses the squared deficit $\alpha$, rather than the
sum of the positive deficits, to count possible common neighbours
of pairs in $T$.

\begin{lemma}
\label{sup:multiple-inputs}
Let $q\ge8$ be even.  Then
\begin{equation}
 \sum_{v\in L}\delta_v=2q-2+t,
 \qquad \alpha\le2q+4t-6+8Q.
 \label{sup:squared-budget}
\end{equation}
If $Q\le q/4$, every pair of vertices of $T$ has a common
neighbour.  For such a pair $u,v$, write
\[
 C=N(u)\cap N(v),\quad c=|C|,\quad
 W=\sum_{x\in C}\delta_x,\quad
 \xi=\varepsilon_u+\varepsilon_v-2(c-1),
 \quad\Theta=(2-c)q+c+W+\xi.
\]
Then $0\le\xi\le2Q$, and
\begin{equation}
 \begin{split}
 (2q-3)W\ge{}&q^2+(5-3c)q-c^2+12c-24\\
 &-(2q-3)\xi-4Q+\frac{\Theta^2}{n-2}.
 \end{split}
 \label{sup:common-deficit}
\end{equation}
In particular, if $c=1$, then
\begin{equation}
 W\ge q/2-2Q.
 \label{sup:singleton-deficit}
\end{equation}
\end{lemma}

\begin{proof}
Write $h=|H|$, $\ell=|L|$, and $k_v=d_T(v)$.
The degree sum gives $\sum_v\delta_v=2q-2$, while each member
of $T$ has deficit $-1$; this proves the first assertion.
For $v\in L$, the local identity gives
$u_v\ge q\delta_v-1-k_v$.
For $v\in H$, parity gives $u_v\ge1-\varepsilon_v$:
if $\varepsilon_v=0$, the graph on its odd neighbourhood is
a matching with an isolated vertex.
We weaken this to $u_v\ge1-k_v-\varepsilon_v$.
For $v\in T$, use $u_v\ge0\ge-k_v$.
Since $\sum_vk_v=(q+2)t$, summation yields
\[
 \sum_vu_v\ge q(2q-2)-n+2h-t-\sum_{v\in H}\varepsilon_v.
\]
If $P_2=\sum_v\binom{d(v)}2$, then
\[
 P_2=\binom n2-\frac12\sum_vu_v
       +\sum_{\{x,y\}}(c_{xy}-1)_+
 \le q m_+-h+\frac t2+4Q.
\]
Here $\sum_{\{x,y\}}(c_{xy}-1)_+\le2Q$ and
$\sum_{v\in H}\varepsilon_v\le4Q$.
Expanding $2P_2-2q m_+$ gives
\[
 \alpha+t-(q+1)(2q-2)\le-2h+t+8Q.
\]
Substitute $h=n-\ell-t$ and
$\ell\le2q-2+t$ to obtain \eqref{sup:squared-budget}.

For the common-neighbour assertions, put
$S=N(u)\cup N(v)$ and $B=V(G)\setminus S$.
If $c=0$, then $|B|=q^2-q-4$.
For $w\ne u,v$, let $b_w=|N(w)\cap B|$.
The excess-codegree bound gives
\[
 \sum_{w\ne u,v}b_w
 \ge2m_+-2(q+2)-2(n-2)-2Q
 =q^3-5q+2-2Q=:s.
\]
There are no two-edge paths with endpoints in $B$ and middle
vertex $u$ or $v$.
The number of such paths is at most $\binom{|B|}{2}+2Q$.
Jensen's inequality therefore gives
\[
 (n-2)\binom{s/(n-2)}2\le\binom{q^2-q-4}{2}+2Q.
\]
The required monotonicity holds because
$s=(q-1)(n-2)-2q-2Q\ge(q-2)(n-2)$ for $q\ge8$ and
$Q\le q/4$.
Twice the left side minus twice the right side equals
\[
 q^2+5q-24-(4q-2)Q+\frac{4(q+Q)^2}{n-2}.
\]
Its polynomial part is at least $11q/2-24>0$, a contradiction.
Hence $c\ge1$.

For this case, $|B|=q^2-q-4+c$ and
\[
 |N(w)\cap S|=c_{uw}+c_{vw}-|N(w)\cap C|.
\]
The contributions of the pair $\{u,v\}$ show that
$0\le\xi\le2Q$ and
\[
 \sum_{w\ne u,v}(c_{uw}+c_{vw})\le2(n-2)+\xi,
 \quad
 \sum_{w\ne u,v}|N(w)\cap C|=\sum_{x\in C}d(x)-2c.
\]
Consequently
\[
 \sum_{w\ne u,v}b_w
 \ge q^3-5q+2+\sum_{x\in C}d(x)-2c-\xi
 =(q-1)(n-2)-\Theta=:s.
\]
The bound $c\le q+2$ and $\xi\le q/2$ gives
$s\ge q^3-15q/2-2>(q-2)(n-2)$ for $q\ge8$.
The same two-path count gives
\[
 (n-2)\binom{s/(n-2)}2
 \le\binom{q^2-q-4+c}{2}+2Q.
\]
Expanding proves \eqref{sup:common-deficit}.
When $c=1$, this inequality and $\xi\le2Q$ imply
\[
 W\ge\frac q2-2Q
       +\frac{(7/2)q-13-4Q}{2q-3}\ge\frac q2-2Q,
\]
where the last numerator is positive for $q\ge8$ and $Q\le q/4$.
\end{proof}

\begin{theorem}
\label{sup:multiple-explicit}
Let $q\ge1600$ be even.  If $G$ has $n$ vertices, $m_+$ edges,
maximum degree at most $q+2$, and at least two vertices of
degree $q+2$, then
\[
 \Nfour(G)>q/12.
\]
\end{theorem}

\begin{proof}
Suppose that $Q\le q/12$.
Every pair of vertices in $T$ has a common neighbour by
Lemma~\ref{sup:multiple-inputs}.
When the common neighbour is unique, its deficit is at least $q/3$,
by \eqref{sup:singleton-deficit}.
There are at most $9\alpha/q^2$ vertices of deficit at least $q/3$,
each of degree at most $q$ and therefore accounting for at most
$q^2/2$ pairs in $T$.
At most $2Q$ pairs have two or more common neighbours.
It follows that
\[
 \binom t2\le\frac92\alpha+2Q,
 \qquad t^2-37t\le\frac{73}{3}q.
\]
The second inequality follows from \eqref{sup:squared-budget}.
It implies $t<q/2$: at $t=q/2$, the difference of the two sides is
\[
 \frac{q^2}{4}-\frac{257}{6}q>0,
\]
and the difference is increasing for $t\ge q/2$.
Hence
\begin{equation}
 \alpha\le2q+4t-6+8Q<\frac{14}{3}q<5q.
 \label{sup:alpha-five-q}
\end{equation}

Choose any two vertices in $T$ and retain the notation $C,c,W$
of Lemma~\ref{sup:multiple-inputs}.
Equation \eqref{sup:pair-cycle-budget} gives
\[
 c\le1+\sqrt{2Q}\le1+\sqrt{q/6}\le\frac12\sqrt q.
\]
Discarding the nonnegative square in \eqref{sup:common-deficit},
and using $\xi\le2Q$, gives
\[
 W\ge\frac{q^2-3cq-c^2-24-q/3}{2q-3}-\frac q6
 \ge\frac q4.
\]
For completeness, the last inequality follows from $c\le\sqrt q/2$
because the difference of its numerators is at least
\[
 \frac{q^2}{6}-\frac32q^{3/2}+\frac23q-24\ge0
 \qquad(q\ge1600).
\]
Replacing negative deficits in $W$ by zero and applying
Cauchy--Schwarz now yields
\[
 \alpha\ge\frac{W^2}{c}
 \ge\frac18q^{3/2}\ge5q,
\]
contrary to \eqref{sup:alpha-five-q}.
\end{proof}

\begin{theorem}
\label{sup:multiple-asymptotic}
Let $q\ge8$ be even, and suppose that $G$ has $n$ vertices,
$m_+$ edges, maximum degree at most $q+2$, and at least two
vertices of degree $q+2$.  Then
\[
 \Nfour(G)>\frac q4-3q^{3/4}.
\]
In particular, this degree configuration forces
$(1/4-o(1))q$ four-cycles as $q\to\infty$.
\end{theorem}

\begin{proof}
The inequality is immediate if its right-hand side is negative.
Suppose otherwise that
$Q\le q/4-3q^{3/4}$.
Then $q\ge12^4=20736$.
Put $d=q/2-2Q$, so $d\ge6q^{3/4}$ and $d^2\ge q$.
For a pair in $T$ with a unique common neighbour,
\eqref{sup:singleton-deficit} gives deficit at least $d$ there.
There are at most $\alpha/d^2$ such vertices, each accounting for
at most $q^2/2$ pairs.  Therefore
\[
 t(t-1)\le\frac{\alpha q^2}{d^2}+4Q
 \le4q^2+4tq+q.
\]
Here we used $\alpha\le4q+4t-6$ from
\eqref{sup:squared-budget}.
At $t=5q$, the left side minus the final right side is
$q^2-6q>0$, and this difference increases for larger $t$.
Thus $t<5q$ and
\begin{equation}
 \alpha<24q.
 \label{sup:alpha-twenty-four-q}
\end{equation}

For any pair in $T$, let $C,c,W$ be as above.
Then $c\le1+\sqrt{2Q}\le\sqrt q$.
Equation \eqref{sup:common-deficit} gives
\begin{align*}
 W
 &\ge d-\frac{3cq+c^2+24+4Q}{2q-3}\\
 &\ge d-\frac{3q^{3/2}+2q+24}{2q-3}
 \ge d-3\sqrt q
 \ge5q^{3/4}.
\end{align*}
All displayed numerical inequalities hold for $q\ge20736$;
for example, the fraction is at most
$2\sqrt q+4/3+16/q\le3\sqrt q$.
Cauchy--Schwarz gives
\[
 \alpha\ge\frac{W^2}{c}\ge25q,
\]
contradicting \eqref{sup:alpha-twenty-four-q}.
\end{proof}

\subsection{The unconditional supersaturation bound}
\label{sup:global-section}

\begin{proof}[Proof of Theorem~\ref{thm:main}]
Let $G_0$ be a spanning subgraph of $G$ with exactly $m_+$ edges.
Theorems~\ref{thm:capped} and~\ref{thm:large-degree} handle
the cases $\Delta(G_0)\le q+1$ and $\Delta(G_0)\ge q+3$.
If $\Delta(G_0)=q+2$, apply
Theorem~\ref{sup:one-high} when it occurs once and
Theorem~\ref{sup:multiple-explicit} when it occurs at least twice.
In every case $12\Nfour(G_0)\ge q-1$.
Since $G_0\subseteq G$, the same bound holds for $G$.
\end{proof}

% Source: sections/degree_bounds.tex
\section{Degree bounds for near-extremal cores}
\label{struct:global-degree-cap-section}

We derive the degree restrictions for a core at edge deficit $b$.
The concentration estimate below first bounds individual deficits;
neighbourhood counts then leave at most one vertex of degree $q+2$.
The incidence-completion theorem in
Appendix~\ref{inc:general-incidence-section} excludes that last vertex
when $q\ge10^9(b+1)^8$.

We use the notation of Section~\ref{sec:counting} and the parameters
in \eqref{eq:parameters}. For a $C_4$-free graph on $n$ vertices,
\begin{equation}
 u_v=q\delta_v-1+a_v.
 \label{struct:local-identity}
\end{equation}
When $q$ is even and $d(v)=q+1$, neighbourhood parity gives
$u_v\ge1$ and hence $a_v\ge2$.

\subsection{Deficit concentration below the extremal bound}

The following estimate permits vertices of degree $q+2$ and does
not require an embedding into a polarity graph.

\begin{lemma}[Deficit concentration]
\label{lem:core-concentration}
Let $q\ge2$ be even, and let $F$ be a $C_4$-free graph on $q^2+q$
vertices with $\Delta(F)\le q+2$.  Put
$T=\{v:d_F(v)=q+2\}$ and $h=|T|$.
For a nonempty set $Z\subseteq L$, write
\[
 k=|Z|,\qquad
 W=\sum_{z\in Z}\delta_z,\qquad
 R=\sum_{v\in L\setminus Z}\delta_v,\qquad
 \chi_R=\sum_{v\in L\setminus Z}\delta_v(\delta_v-1).
\]
Then
\begin{align}
 (q+k+2)(W-R)+\chi_R
 &\le -2q^2+(k^2+2k-2)q+2k(k+2)
       +(k+2)h+e_F(Z,T) \notag\\
 &\le -2q^2+(k^2+2k-2)q+2k(k+2)+2(k+1)h.
 \label{eq:core-concentration}
\end{align}
\end{lemma}

\begin{proof}
Set
\[
 B=L\cup T\cup\bigcup_{z\in Z}N_F(z),
 \qquad X=V(F)\setminus B.
\]
Every vertex of $X$ has degree $q+1$ and has no neighbour in $Z$.
The graph induced by a neighbourhood in a $C_4$-free graph is a
matching together with isolated vertices.  Since $q+1$ is odd,
each $v\in X$ has an uncovered partner in $N_F(v)$, and this
partner does not belong to $Z$.  Thus
\[
 |\{z\in Z:N_F(v)\cap N_F(z)=\varnothing\}|
 \le u_v-1=a_v-2.
\]
On summing over $X$, the positive-deficit contributions come only
from $L\setminus Z$.  Discarding the negative contributions from
$T$ gives
\[
 \sum_{v\in X}(a_v-2)
 \le \sum_{w\in L\setminus Z}\delta_wd_F(w)-2|X|
 =qR-\chi_R-2|X|.
\]
For each $z\in Z$, at most $|B|-1$ uncovered partners lie in $B$.
Also $a_z\ge-d_T(z)$.  Hence
\[
 -k+qW-e_F(Z,T)
 \le\sum_{z\in Z}u_z
 \le qR-\chi_R-2|X|+k(|B|-1).
\]
Using $|X|=n-|B|$, we obtain
\begin{equation}
 q(W-R)+\chi_R+2n\le(k+2)|B|+e_F(Z,T).
 \label{eq:core-concentration-intermediate}
\end{equation}
Every positive deficit is an integer, so
\[
 |B|\le |L|+h+\sum_{z\in Z}d_F(z)
 \le k+R+h+k(q+1)-W
 =kq+2k+h-(W-R).
\]
Substitution in \eqref{eq:core-concentration-intermediate}, together
with $n=q^2+q$, proves the first inequality in
\eqref{eq:core-concentration}.  The second follows from
$e_F(Z,T)\le kh$.
\end{proof}

\begin{corollary}[An individual deficit bound]
\label{cor:core-individual-deficit}
Under the hypotheses of Lemma~\ref{lem:core-concentration}, suppose
$e(F)=m_0-b$, where $b\ge0$.  Every $z\in L$ satisfies
\begin{equation}
 2\delta_z\le 2b+h+7+\frac{4h-15}{q+3}.
 \label{eq:core-individual-deficit}
\end{equation}
In particular, if $e(F)=m_0$ and $\Delta(F)\le q+1$, then
$d_F(v)\ge q-2$ for every vertex.  For even $q\le10$, the latter
bound improves to $d_F(v)\ge q-1$.
\end{corollary}

\begin{proof}
The degree sum gives
\[
 \sum_v\delta_v=2q+2b,\qquad
 \sum_{v\in L}\delta_v=2q+2b+h.
\]
Take $Z=\{z\}$ in Lemma~\ref{lem:core-concentration}.
Then $W-R=2\delta_z-2q-2b-h$.  After discarding $\chi_R\ge0$,
we obtain
\[
 (q+3)(2\delta_z-2q-2b-h)\le-2q^2+q+6+4h.
\]
The identity
$-2q^2+q+6=(-2q+7)(q+3)-15$ yields
\eqref{eq:core-individual-deficit}.
When $b=h=0$, its right side is strictly less than $7$, so
the integer $\delta_z$ is at most three.  For $q\le10$ the
right side is strictly less than $6$, giving $\delta_z\le2$.
\end{proof}

\subsection{At most one high vertex in a linear edge window}

\begin{lemma}[A near-extremal maximum-degree bound]
\label{struct:maximum-degree-two}
Let $q\ge8$ be an integer and $0\le b\le q/16$.
If $F$ is $C_4$-free with $n$ vertices and $m_0-b$ edges, then
$\Delta(F)\le q+2$.
\end{lemma}

\begin{proof}
Suppose a vertex has degree $D\ge q+3$, and put $a=n-1$ and
$m=m_0-b$.  Count two-edge paths whose endpoints lie outside its
neighbourhood.  For each other middle vertex, the number of neighbours
outside that neighbourhood is at least its degree minus one.
Consequently, Jensen's inequality gives
\begin{equation}
 a\binom{(2m-D-a)/a}{2}\le\binom{n-D}{2}.
 \label{struct:single-neighbourhood-jensen}
\end{equation}
Here and below $\binom{x}{2}=x(x-1)/2$ for real $x$.
The monotonicity step in this use of Jensen is legitimate: for
$D\le n-1$, the argument's numerator is at least
\[
 2m-2(n-1)=q^3-3q+2-2b
          >(q-2)(n-1),
\]
because the difference is $q^2-2b>0$.

Let $J(D)$ be the left side of
\eqref{struct:single-neighbourhood-jensen} minus its right side.
It is concave as a function of $D$, since its quadratic coefficient
is $1/(2a)-1/2<0$.
At the first endpoint, direct expansion gives
\[
 2J(q+3)=q^2-(4b+1)q+2b-10
          +\frac{4(q+b+1)^2}{q^2+q-1}>0.
\]
Indeed, its polynomial part is at least
$3q^2/4-q-10>0$.
At $D=n-1$, the right side of
\eqref{struct:single-neighbourhood-jensen} is zero, while its left
side is positive.  Concavity makes $J$ positive on the entire
interval, a contradiction.
\end{proof}

\begin{lemma}[Two high vertices force a large common deficit]
\label{struct:high-common-deficit}
Let $q\ge8$ and $0\le b\le q/16$, and let $F$ be as in
Lemma~\ref{struct:maximum-degree-two}.
Any two vertices of degree $q+2$ have exactly one common neighbour
$z$, and
\begin{equation}
 \delta_z\ge\frac{3q}{8}-1.
 \label{struct:high-overlap-lower}
\end{equation}
\end{lemma}

\begin{proof}
Write $x,y$ for the high vertices and
$B=V(F)\setminus(N(x)\cup N(y))$.
There is no two-edge path with endpoints in $B$ and middle vertex
$x$ or $y$.  For $v\ne x,y$, let $r_v=|N(v)\cap B|$.

First suppose $N(x)\cap N(y)=\varnothing$.
Then $|B|=q^2-q-4$, and the codegree bound gives
\[
 \sum_{v\ne x,y}r_v
 \ge 2m-2(q+2)-2(n-2)=q^3-5q-2b=:S_0.
\]
Also $S_0>(q-2)(n-2)$, since the difference is
$q^2-q-2b-4>0$.
Thus the path count and Jensen imply
\[
 (n-2)\binom{S_0/(n-2)}2\le\binom{q^2-q-4}{2}.
\]
Twice the left side minus twice the right side is
\[
 q^2+(1-4b)q+6b-18
       +\frac{4(q+b+1)^2}{n-2}>0.
\]
Its polynomial part is at least $3q^2/4+q-18>0$.
This contradiction rules out disjoint neighbourhoods.

Since $F$ is $C_4$-free, there is now a unique common neighbour $z$.
Put $w=\delta_z$.  Inclusion--exclusion gives
\begin{align*}
 \sum_{v\ne x,y}r_v
 &\ge 2m-2(q+2)-2(n-2)+d(z)-2\\
 &=q^3-4q-1-2b-w\\
 &=(q-1)(n-2)-(q+3+2b+w)=:S_1.
\end{align*}
Because $d(z)\ge2$, one has $w\le q-1$ and $S_1\ge S_0$.
The same Jensen argument, with $|B|=q^2-q-3$, yields
\begin{equation}
 (2q-3)w\ge q^2-(4b+2)q+6b-7
       +\frac{(q+3+2b+w)^2}{n-2}.
 \label{struct:exact-high-overlap}
\end{equation}
For $q\ge8$ and $b\le q/16$, the polynomial on the right is
at least $3q^2/4-13q/8-7$.
Subtracting $(2q-3)(3q/8-1)$ from this lower bound gives
$3q/2-10>0$.
Discarding the square term proves \eqref{struct:high-overlap-lower}.
\end{proof}

\begin{lemma}[Signed deficit-square budget]
\label{struct:signed-square-budget}
Let $q$ be even and suppose $F$ is $C_4$-free with $n$ vertices,
$m_0-b$ edges, and maximum degree at most $q+2$.
Let $T,H,L$ be the vertices of degree $q+2$, degree $q+1$, and
degree at most $q$, respectively.  Put $h=|T|$ and
$\alpha=\sum_{v\in L}\delta_v^2$.
Then
\begin{equation}
 \sum_{v\in L}\delta_v=2q+2b+h,
 \qquad
 \alpha\le 2bq+6b+4q+4h.
 \label{struct:signed-square-bound}
\end{equation}
\end{lemma}

\begin{proof}
Let $D=\sum_v\delta_v=2q+2b$ and $k_v=|N(v)\cap T|$.
Equation~\eqref{struct:local-identity} gives
$u_v\ge q\delta_v-1-k_v$ on $L$.
On $H$, neighbourhood parity gives $u_v\ge1\ge1-k_v$;
on $T$, use $u_v\ge0\ge-k_v$.
Since $\sum_vk_v=(q+2)h$, summation gives
\[
 \sum_vu_v\ge qD-n+2|H|-h.
\]
On the other hand, summing the exact local identity gives
\[
 \sum_vu_v=(2q+1)D-n-(\alpha+h),
\]
because
$\sum_va_v=\sum_v\delta_vd(v)=(q+1)D-\sum_v\delta_v^2$.
Comparison yields $\alpha\le(q+1)D-2|H|$.
Finally $|H|=n-h-|L|$ and
$|L|\le\sum_L\delta_v=D+h$, so
\[
 \alpha\le(q+3)D-2n+4h=2bq+6b+4q+4h.
\]
The first identity in \eqref{struct:signed-square-bound} follows
directly from the negative deficit $-1$ at each member of $T$.
\end{proof}

\begin{theorem}[One-edge degree reduction in a linear window]
\label{struct:at-most-one-high}
Let $q\ge2048$ be even, and let $0\le b\le q/16$ be an integer.
If $F$ is $C_4$-free with $n$ vertices and $m_0-b$ edges, then
\[
 \Delta(F)\le q+2,
 \qquad |\{v:d(v)=q+2\}|\le1.
\]
In particular, deleting at most one edge gives a spanning
$C_4$-free graph of maximum degree at most $q+1$ and with at least
$m_0-b-1$ edges.  Every vertex of $F$ has degree at least $q-b-2$.
\end{theorem}

\begin{proof}
The maximum-degree assertion is
Lemma~\ref{struct:maximum-degree-two}.
Suppose $h\ge2$.  Since $q\ge24$, every pair of high vertices
has its unique common neighbour in
$L_*:=\{v:\delta_v\ge q/3\}$.
The positive deficit sum bounds
$|L_*|\le3(2q+2b+h)/q$.
Every vertex of $L_*$ has degree at most $2q/3+1\le q$, so it
serves as the common neighbour of at most $q^2/2$ high pairs.
Therefore
\[
 \binom h2\le\frac32q(2q+2b+h)
             \le\frac{51}{16}q^2+\frac32hq.
\]
This implies $h<5q$: at $h=5q$ the left side minus the final
right side is $29q^2/16-5q/2>0$, and that difference increases
for $h\ge5q$.
Lemma~\ref{struct:signed-square-budget} consequently gives
\[
 \alpha<\frac18q^2+\frac{195}{8}q.
\]
Choose any high pair and its common neighbour $z$.
Equation~\eqref{struct:high-overlap-lower} gives
\[
 \alpha\ge\delta_z^2\ge
       \left(\frac{3q}{8}-1\right)^2.
\]
The last lower bound minus the preceding strict upper bound is
\[
 \frac{q^2}{64}-\frac{201q}{8}+1>0
 \qquad(q\ge2048),
\]
a contradiction.

The edge-deletion assertion is immediate.
For the minimum degree, Corollary~\ref{cor:core-individual-deficit} gives
\[
 2\delta_v\le 2b+h+7+\frac{4h-15}{q+3}.
\]
Since $h\le1$, this is strictly less than $2b+8$.
The integer $\delta_v$ is therefore at most $b+3$.
\end{proof}

\subsection{Excluding the last high vertex for a fixed deficit}

\begin{theorem}[Automatic degree cap for a fixed edge deficit]
\label{struct:automatic-fixed-deficit-cap}
For every fixed nonnegative integer $b$, there is $q_0(b)$ such
that the following holds for every even $q\ge q_0(b)$.
If $F$ is $C_4$-free with $q^2+q$ vertices and $m_0-b$ edges, then
\begin{equation}
 \Delta(F)\le q+1.
 \label{struct:automatic-cap}
\end{equation}
One sufficient explicit choice, using the numerical sufficient
conditions in the fixed-parameter incidence-completion theorem,
is
\begin{equation}
 q_0(b)=10^9(b+1)^8.
 \label{struct:explicit-degree-threshold}
\end{equation}
\end{theorem}

\begin{proof}
Put $B=b+1$ and suppose $q\ge10^9B^8$.
Then $q\ge2048$ and $b\le q/16$, so
Theorem~\ref{struct:at-most-one-high} applies.
The incidence-completion inequalities are checked at the end of
the proof with this same explicit bound.
Suppose its one remaining exceptional vertex $y$ exists, with
$d(y)=q+2$.
Let $H$ be the degree-$(q+1)$ vertices, $L$ the positive-deficit
vertices, and put
\[
 \sigma=\sum_{v\in L}(\delta_v-1),\qquad
 \tau=\sum_{v\in N(y)\cap L}(\delta_v-1),\qquad
 k=|N(y)\cap H|.
\]
The degree sum gives
\[
 \sum_{v\in L}\delta_v=2q+2b+1,\qquad
 |H|=q^2-q-2-2b+\sigma.
\]
Because $y$ is the only high vertex, its neighbourhood consists of
$k$ full vertices and $q+2-k$ low vertices.  Its local identity is
\begin{equation}
 u_y=-q-1+a_y
     =-q-1+(q+2-k+\tau)=1-k+\tau.
 \label{struct:single-high-low-service}
\end{equation}
Thus $k\le1+\tau\le1+\sigma$.

Delete $y$ and call the resulting graph $F_0$.
It has $N-2$ vertices.  Every full vertex outside $N(y)$ remains
of degree $q+1$, so $F_0$ has at least
\begin{equation}
 |H|-k\ge q^2-q-3-2b
       =N-2(q+1)+\binom22-(2b+3)
 \label{struct:clean-full-count}
\end{equation}
full-degree vertices.
Choose exactly this many and call their set $C$.

Consider the incidence system with point set $C$ and indexed
lines
\[
 S_v=N_{F_0}(v)\cap C\qquad(v\in V(F_0)).
\]
Each point is on exactly $q+1$ indexed lines, and two different
indexed lines meet in at most one point by $C_4$-freeness.
Its parameters are those of the fixed-parameter completion theorem
with
\begin{equation}
 s=2,\qquad t=2b+3,\qquad K=s+t=2b+5.
 \label{struct:completion-parameters}
\end{equation}
For completeness, the required uncovered-degree bound follows
automatically.  The shortest-line packing lemma gives
$|S_v|\ge q+1-K$ for every $v$.
For this paragraph, recompute the deficits in the smaller graph:
$\delta_x^{(0)}=q+1-d_{F_0}(x)$ and
$a_x^{(0)}=\sum_{v\in N_{F_0}(x)}\delta_v^{(0)}$.
The line-size bound gives $\delta_x^{(0)}\le K$.
Every $x\in C$ has at most $K$ neighbours outside $C$, while
all neighbours in $C$ have deficit zero.  Its weighted neighbour
deficit is at most $K^2$.
The exact local identity at the order $N-2$ is therefore
\[
 u_x^{(0)}=a_x^{(0)}-2\le K^2-2,
\]
where $u_x^{(0)}$ counts uncovered partners in $F_0$.
Thus the uncovered-pair graph on $C$ has maximum degree at most
$D=K^2$.
The fixed-parameter incidence-completion theorem embeds all the
indexed lines, with their exact incidences on $C$, in a projective
plane $\Pi$ of order $q$.
Denote their distinct image lines by $\ell_v$.

There are exactly two plane lines not among the indexed lines.
Every point of $C$ already lies on its full pencil of $q+1$
indexed lines, so no point of $C$ lies on either missing line.
Their union has $2q+1$ points, whereas
\[
 |V(\Pi)\setminus C|=2q+4+2b.
\]
There are therefore exactly $t=2b+3$ further points outside $C$
and outside the union of the two missing lines.
An indexed line meets that union in at most two points and hence
contains at most $t+2=K$ points outside $C$.

Now take the $q+2$ distinct indexed lines
\[
 \mathcal F=\{\ell_v:v\in N_F(y)\}.
\]
They intersect pairwise outside $C$.
Indeed, a point $x\in C$ on both $\ell_v$ and $\ell_w$ would
give the four-cycle $y,v,x,w$ in $F$.
Lemma~\ref{struct:bounded-pencil} makes all $q+2$ lines concurrent
once $q+1>K(K-1)$.
But a point of a plane of order $q$ lies on exactly $q+1$ lines.
This contradiction excludes $y$ and proves the fixed-$b$ assertion.

We finally verify the explicit sufficient choice
\eqref{struct:explicit-degree-threshold}.
For the constants in the proof of the fixed-parameter
incidence-completion theorem, the parameters in
\eqref{struct:completion-parameters} satisfy
\[
 \begin{gathered}
 K\le5B,\quad A_0\le12B,\quad B_0\le48B^2,\quad Y_0\le96B^2,\\
 \mu=D=K^2\le25B^2,\quad C_1\le198B^3,\quad a_0\le106B^2.
 \end{gathered}
\]
The packing constant is $C_{2,t}=t(t-1)\le9B^2$.
The bad-pair deletion threshold is at most
$352800B^7$.
The two Metsch thresholds are at most $952B^3$ and $1938B^4$,
and the extra exact-clique threshold is at most $2388B^4$.
The restoration-of-indices condition follows from
$q>9221B^4$.
Finally, for the Beutelspacher--Metsch polynomial
$f(a)=6a^4+9a^3+19a^2+8a$,
\[
 f(a_0)\le f(106)B^8
        =768419652B^8<4\cdot10^9B^8.
\]
The remaining inequalities in
\eqref{inc:completion-packing}--\eqref{inc:BM-bound},
including the shortest-line and clique-size bounds, hold for
$q\ge10^9B^8$.  This range also gives $q+1>K(K-1)$, as required
for the final pencil argument.
\end{proof}

% Source: sections/polarity_stability.tex
\section{Polarity stability at a prescribed edge deficit}
\label{stab:section}

We prove Theorem~\ref{stab:main}. Put $B=b+1$.
The degree bounds of Section~\ref{struct:global-degree-cap-section}
reduce the argument to nonnegative deficits.
A dichotomy for their total excess and an exact second-moment
identity produce a bounded set of vertices whose deletion permits
incidence completion. We then restore those vertices and their
incident edges inside the resulting polarity graph.

\subsection{A dichotomy for the total excess deficit}

Throughout the preliminary argument let $b\ge0$ be an integer,
suppose $q$ is even with $q\ge100B^2$, and let $F$ be a $C_4$-free graph satisfying
\begin{equation}
 |V(F)|=N-1,\qquad e(F)=m_0-b,\qquad
 q-b-2\le d_F(v)\le q+1.
 \label{stab:degree-hypotheses}
\end{equation}
Set
\[
 \begin{gathered}
 \delta_v=q+1-d_F(v),\quad
 H=\{v:\delta_v=0\},\quad L=\{v:\delta_v>0\},\\
 r_v=|N_F(v)\cap L|,\qquad
 a_v=\sum_{w\in N_F(v)}\delta_w.
 \end{gathered}
\]
Write $u_v$ for the number of other vertices having no common neighbour
with $v$, and $u_{HH}$ for the number of uncovered unordered pairs
inside $H$.  Define
\[
 \sigma=\sum_{v\in L}(\delta_v-1),\quad
 \chi=\sum_{v\in L}\delta_v(\delta_v-1),\quad
 \Omega=\sum_{v\in L}\delta_vr_v,\quad
 \eta=\sum_{v\in H}(a_v-2).
\]
The degree sum, the local two-path identity, and weighted counting
between $L$ and $H$ give
\begin{align}
 \sum_{L}\delta_v&=2q+2b,&
 |L|&=2q+2b-\sigma,&
 |H|&=q^2-q-2b+\sigma,\label{stab:sizes}\\
 u_v&=q\delta_v-1+a_v,\label{stab:local}\\
 \eta+\chi+2\sigma+\Omega&=2Bq+4b.
 \label{stab:budget}
\end{align}
Indeed, $\sum_Ha_v=q(2q+2b)-\chi-\Omega$, and subtracting
$2|H|$ proves the budget.  Every full vertex has $a_v\ge2$:
its odd neighbourhood induces a matching and isolated vertices, so
at least one neighbour is uncovered from it.  In particular all terms
on the left side of \eqref{stab:budget} are nonnegative.

A full vertex is good if $a_v=2$ and bad otherwise.  A good vertex
has exactly one uncovered partner $f(v)$, and $vf(v)$ is an edge.
For good vertices $v,w$, the common-neighbour matrix identity yields
\begin{equation}
 A_{v,f(w)}=A_{f(v),w}.
 \label{stab:good-commutator}
\end{equation}
To see this directly, write $U$ for the uncovered-pair adjacency
matrix.  Since $F$ is $C_4$-free,
$A^2=qI+J-U-\operatorname{diag}(\delta)$; commuting with $A$ gives
$[A,U]_{vw}=(\delta_w-\delta_v)(1-A_{vw})$.  At two good vertices,
the corresponding rows of $U$ are unit vectors, giving
\eqref{stab:good-commutator}.

\begin{lemma}[Bounded exceptional capacity]
\label{stab:exceptional-capacity}
Let $g$ be the number of good vertices whose uncovered partner is good,
and let
\[
 G_0=\{v\in H:v\text{ is good and }f(v)\in L\},\qquad
 p=|H\setminus G_0|.
\]
Then
\begin{equation}
 g\le2B,\qquad p\le2\eta+2B,\qquad u_{HH}\le2\eta+B.
 \label{stab:exceptional-bounds}
\end{equation}
If $t=|\{v:\delta_v=2\}|$ and
$A_*=\sum_{\delta_v\ge3}\delta_v$, then
\begin{equation}
 |G_0|\le(q+b-t-A_*/2)^2+t(q-1).
 \label{stab:support-capacity}
\end{equation}
\end{lemma}

\begin{proof}
If good vertices $u,v$ are uncovered from one another, each is the
other's partner. If another good vertex $w$ were adjacent to $u$,
equation~\eqref{stab:good-commutator}, applied to $v,w$, would give
$vf(w)\in E(F)$. The vertices $u,w,f(w),v$ would form a
four-cycle. They are distinct because $f(w)\ne w$ and uniqueness
of the partners at $u,v$ excludes $f(w)\in\{u,v\}$.
Since $a_u=2$, at most two neighbours of $u$ are low, and it has
at least $q-2$ bad full neighbours.  If $2B+1$ good vertices had
good partners, their bad-neighbour sets would have union of size at
least
\[
 (2B+1)(q-2)-\binom{2B+1}{2}>2Bq+4b\ge\eta.
\]
Here intersections of any two neighbourhoods have size at most one,
and the strict inequality follows from
$q>2B^2+9B-2$.  The number of bad full vertices is at most $\eta$,
so this is impossible and $g\le2B$.

For a bad full vertex write $s_v=a_v-2\ge1$; then $u_v=s_v+1$.
The number of its adjacent uncovered partners is odd.  It is at most
$s_v$ if $s_v$ is odd and at most $s_v+1$ if $s_v$ is even.
Let $B_0$ be the number of bad vertices and $B_{\rm even}$ the number
with positive even $s_v$.  Good vertices outside $G_0$ either have a
bad partner or are among the $g$ vertices just counted.  Therefore
\[
 p\le B_0+\eta+B_{\rm even}+g\le2\eta+2B,
\]
because $B_0+B_{\rm even}\le\sum s_v=\eta$.
Every uncovered full--full pair either touches a bad vertex or is
one of the $g/2$ good--good pairs.  Thus
$u_{HH}\le\eta+B_0+g/2\le2\eta+B$.

Put $X=f(G_0)$.  A vertex $v\in G_0$ cannot have a second neighbour
in $X$: applying \eqref{stab:good-commutator} to $v$ and a vertex
partnered to that neighbour would produce a four-cycle.
If $\delta_{f(v)}=1$, the two low neighbours of $v$ are unit-deficit
vertices, one in $X$ and one outside $X$.  Different such full
vertices give different pairs.  There are $2q+2b-2t-A_*$
unit-deficit vertices, so their number is at most
$(q+b-t-A_*/2)^2$.  If $\delta_{f(v)}=2$, its partner is the sole
low neighbour of $v$ and supports at most $q-1$ vertices.
No deficit at least three can neighbour a good full vertex.
This proves \eqref{stab:support-capacity}.
\end{proof}

\begin{lemma}[Small or nearly full excess deficit]
\label{stab:sigma-dichotomy}
Put $C=8b+10$.  Under \eqref{stab:degree-hypotheses}, either
\begin{equation}
 \sigma<C\qquad\text{or}\qquad\sigma>q-C.
 \label{stab:sigma-dichotomy-formula}
\end{equation}
In the second case, $F$ has at least $q^2-10B$ full-degree vertices.
\end{lemma}

\begin{proof}
The definitions imply $t+A_*\ge\sigma$ and
$\sigma/2\le t+A_*/2\le\sigma$.
For $\sigma\ge2b$, expansion of \eqref{stab:support-capacity} gives
\begin{align*}
 p&\ge(t+A_*-2b-1)q-(t+A_*/2-b)^2-2b+\sigma+t\\
  &\ge(\sigma-2b-1)q-(\sigma-b)^2-2b.
\end{align*}
Use $p\le2\eta+2B\le4Bq+8b+2B$ to obtain
\begin{equation}
 (\sigma-6b-5)q-(\sigma-b)^2\le12b+2.
 \label{stab:sigma-quadratic}
\end{equation}
The left side is concave as a function of $\sigma$.  At the endpoints
of $[C,q-C]$ it equals, respectively,
\[
 (2b+5)q-(7b+10)^2,\qquad
 (4b+5)q-(9b+10)^2.
\]
Both exceed $12b+2$ for $q\ge100B^2$: each is at least
$5q-100B^2\ge400B^2$.  Also $C\ge2b$ and $q\ge2C$.
Thus this entire interval is excluded.  In the second alternative,
\eqref{stab:sizes} gives $|H|>q^2-2b-C=q^2-10B$.
\end{proof}

\subsection{Signed moments and a bounded deletion set}

Define
\[
 w_v=\begin{cases}
 r_v+\delta_v-1,&v\in L,\\
 r_v-2,&v\in H,
 \end{cases}
 \qquad T=\sum_{v\in L}(\delta_v-1)r_v.
\]
For every vertex,
\begin{equation}
 d_H(v)=q-w_v-\mathbf1_H(v).
 \label{stab:weight-service}
\end{equation}

\begin{lemma}[General signed moments]
\label{stab:moments}
Under \eqref{stab:degree-hypotheses},
\begin{align}
 \sum_vw_v&=2Bq+4b-(q+2)\sigma,
 \label{stab:first-moment}\\
 \sum_vw_v^2
 &=q^2+(6b+1-\sigma)q+(2b-\sigma)^2+2b+\sigma\notag\\
 &\hspace{9mm}-2\chi-2\eta-2T-2u_{HH}.
 \label{stab:second-moment}
\end{align}
If $\sigma<C=8b+10$ and $w_v^+=\max\{w_v,0\}$, then
\begin{equation}
 \sum_vw_v^+\le(2B+1)q,\qquad
 \sum_v(w_v^+)^2\ge q^2-32Bq.
 \label{stab:positive-moments}
\end{equation}
\end{lemma}

\begin{proof}
Write $\ell=|L|$, $h=|H|$, and $e_L=e(F[L])$.
Since $\sum_vr_v=\sum_Ld(v)=q\ell-\sigma$, summing the definitions
of $w_v$ gives $\sum w_v=q\ell-2h$, which is
\eqref{stab:first-moment}.

Let $u_{LL}$ and $u_{LH}$ count uncovered pairs of the indicated
types.  Summing \eqref{stab:local} over the two layers gives
\[
 2u_{LL}+u_{LH}=q(2q+2b)-\ell+\Omega,
 \qquad 2u_{HH}+u_{LH}=h+\eta.
\]
Hence
\begin{equation}
 2u_{LL}=q^2+(2b-1)q+\Omega-\eta+2u_{HH}.
 \label{stab:low-holes}
\end{equation}
Counting covered pairs in $L$ by their unique common neighbour yields
\[
 \sum_vr_v^2=q\ell-\sigma+\ell(\ell-1)-2u_{LL}.
\]
Now $\sum_L(\delta_v-1)^2=\chi-\sigma$,
$\sum_Hr_v=q\ell-\sigma-2e_L$, and $\Omega=2e_L+T$.
Replacing $r_v$ by its defining weight therefore gives
\begin{align*}
 \sum_vw_v^2
 &=q\ell-\sigma+\ell(\ell-1)-2u_{LL}
       +2T+\chi-\sigma-4(q\ell-\sigma-2e_L)+4h\\
 &=\ell(\ell-1)-3q\ell+2\sigma+\chi+4\Omega-2T+4h-2u_{LL}.
\end{align*}
Substitute \eqref{stab:low-holes}, \eqref{stab:budget}, and
\eqref{stab:sizes}.  Direct expansion gives
\eqref{stab:second-moment}.

Every low weight is nonnegative.  A full vertex has $r_v\ge1$, so
the only negative value is $-1$.  Such a vertex has just one low
neighbour, of deficit at least two.  If $a_-$ counts the negative
weights, then
\[
 a_-\le\sum_{\delta_v\ge2}d_H(v)\le\sigma q.
\]
Thus $\sum w_v^+\le2Bq+4b\le(2B+1)q$.
Also $\sum(w_v^+)^2=\sum w_v^2-a_-$.
Use $\delta_v\le b+3=B+2$, $\chi\le(B+2)\sigma$,
$T\le\Omega$, and $u_{HH}\le2\eta+B$ in the second moment.
Discarding its nonnegative constant terms gives
\begin{align*}
 \sum_v(w_v^+)^2
 &\ge q^2-(6b+11+2\sigma)q-2(B+2)\sigma-24b-2B\\
 &\ge q^2-31Bq-78B^2
 \ge q^2-32Bq.
\end{align*}
The first inequality uses $6\eta+2T\le6(\eta+\Omega)
\le12Bq+24b$.  The last two use $\sigma<C=8B+2$ and
$q\ge100B^2$.  This proves \eqref{stab:positive-moments}.
\end{proof}

\begin{lemma}[The largest $k$ weights]
\label{stab:largest-k}
Let $x_1\ge x_2\ge\cdots\ge0$, let $k\ge1$, and suppose
$\sum_i x_i\le kq$.  Put $W=\sum_{i=1}^k x_i$, adjoining zero
terms if necessary.  If $W\le q$, then
\[
 \sum_i x_i^2\le qW.
\]
\end{lemma}

\begin{proof}
Put $a=x_k$.  For fixed $a,W$, convexity bounds the sum of the first
$k$ squares by $(W-(k-1)a)^2+(k-1)a^2$.  The remaining terms are
at most $a$, so their squared sum is at most $a(kq-W)$.
The resulting bound is the convex quadratic
\[
 W^2+\{kq-(2k-1)W\}a+k(k-1)a^2,
 \qquad 0\le a\le W/k.
\]
At its endpoints the values are $W^2$ and $qW$.  Since $W\le q$,
both are at most $qW$.  The same calculation, or the bound
$\sum x_i^2\le x_1\sum x_i$, covers $k=1$.
\end{proof}

\begin{proposition}[Concentration in a bounded vertex set]
\label{stab:deletions}
If \eqref{stab:degree-hypotheses} holds and $\sigma<C$, put
$k=2B+1$.  There is a set $S$ of $k$ vertices such that
\[
 \sum_{v\in S}w_v\ge q-32B.
\]
In $F_0=F-S$, at least
\begin{equation}
 q^2-kq-(34B-2)
 =N-(k+1)(q+1)+\binom{k+1}{2}-t_0,
 \qquad t_0=2B^2+35B-2,
 \label{stab:clean-full-count}
\end{equation}
vertices have degree $q+1$ and were adjacent to no vertex of $S$.
\end{proposition}

\begin{proof}
Apply Lemma~\ref{stab:largest-k} and \eqref{stab:positive-moments}.
If the largest-$k$ sum is at most $q$, it is at least $q-32B$;
otherwise this conclusion is immediate.  The chosen positive-part
weights can be realized by distinct vertices of nonnegative actual
weight. Indeed, $\sigma<8b+10$ and $q\ge100(b+1)^2$ imply
\[
 |L|=2q+2b-\sigma>2q-6b-10>2b+3=k.
\]
The low vertices all have nonnegative weight and can replace
any zero-weight choices at vertices of negative actual weight.

Every vertex in $H\setminus(S\cup N_F(S))$ remains full in $F_0$.
Using \eqref{stab:weight-service}, their number is at least
\[
 |H|-|S\cap H|-\sum_{v\in S}d_H(v)
 =|H|-kq+\sum_{v\in S}w_v
 \ge q^2-kq-2b+\sigma-32B.
\]
Discarding $\sigma\ge0$ gives \eqref{stab:clean-full-count}.
\end{proof}

\subsection{Completion and reinsertion}

\begin{lemma}[A polarity with few extra absolute points]
\label{stab:orthogonal-host}
Let $P$ be the graph of a polarity of a plane of even order $q$.
If $e(P)\ge M-b$ and $q>4b^2$, then its absolute points form a line
of exactly $q+1$ points, and $e(P)=M$.
\end{lemma}

\begin{proof}
The elementary even-order polarity lemma shows that its absolute set
$\mathcal A$ is a blocking set, that distinct absolute points are
nonadjacent, and that $|\mathcal A|\ge q+1$.
The exact edge formula gives $|\mathcal A|\le q+1+2b$.
Write $|\mathcal A|=q+d$, so $1\le d\le2b+1$.
We recall the standard counting argument for the blocking-set bound
of Bruen~\cite{Bruen1970}.

Suppose no whole line lies in $\mathcal A$, and put
$r_\ell=|\ell\cap\mathcal A|$.
Choose a point of $\ell$ outside $\mathcal A$.
The other $q$ lines through that point each require a different
point of $\mathcal A$ outside $\ell$, so $1\le r_\ell\le d$.
Counting incidences and ordered collinear pairs gives
\[
 \sum_\ell r_\ell=(q+d)(q+1),\qquad
 \sum_\ell r_\ell(r_\ell-1)=(q+d)(q+d-1).
\]
Consequently
\[
 0\ge\sum_\ell(r_\ell-1)(r_\ell-d)
   =q\{q-(d-1)^2\}>0,
\]
a contradiction.  Thus $\mathcal A$ contains a line.
There is no additional absolute point $x$ outside it: the polar line
of $x$ would meet this absolute line at another absolute point,
making two distinct absolute points adjacent.  It follows that
$|\mathcal A|=q+1$, and the edge formula gives $e(P)=M$.
\end{proof}

\begin{lemma}[Uniform completion bounds]
\label{stab:uniform-completion-bounds}
Let $B\ge1$ be an integer and suppose $q\ge10^{18}B^{16}$.
For either parameter choice
\begin{equation}
 (s,t)=(1,10B)
 \quad\hbox{or}\quad
 (s,t)=(2B+2,\,2B^2+35B-2),
 \label{stab:uniform-parameter-choices}
\end{equation}
put $K=s+t$ and $D=K^2$.
All numerical conditions
\eqref{inc:completion-packing}--\eqref{inc:BM-bound}
for Theorem~\ref{inc:fixed-parameter-completion} hold.
The polarity-extension condition $q>(K+2)^2$ in
Lemma~\ref{geo:bounded-polarity-extension} also holds.
Moreover,
\begin{align}
 q&\ge10^9B^8,\qquad q\ge100B^2,\qquad
 q\ge2048,\qquad B-1\le q/16,\label{stab:uniform-degree-range}\\
 q&>4(B-1)^2,\qquad
 q-3B-2>K(K-1),\qquad
 q-6B-4>2B^2+6B+1.
 \label{stab:uniform-reinsertion-range}
\end{align}
\end{lemma}

\begin{proof}
Both choices in \eqref{stab:uniform-parameter-choices} satisfy
\[
 s\le4B,\quad t\le35B^2,\quad K\le39B^2,\quad
 |\beta|\le34B,
\]
where $\beta=(s-1)(s-2)/2-t$.
The constants in the proof of
Theorem~\ref{inc:fixed-parameter-completion} therefore satisfy
\[
 \begin{gathered}
 A_0\le80B^2,\quad B_0\le2880B^4,\quad Y_0\le5760B^4,\\
 \mu=D\le1521B^4,\quad C_1\le65100B^6,\quad
 a_0\le7129B^4.
 \end{gathered}
\]
In particular, $s^4+2s^3+1\le385B^4$ and
$|C_{s,t}|\le1492B^3$.
Substitution gives the following bounds for the sufficient
thresholds in the incidence-completion proof.
\begin{center}
\begin{tabular}{@{}ll@{}}
\toprule
Condition & Upper bound on its threshold for $q$\\
\midrule
\eqref{inc:completion-packing} & $385B^4$ and $1492B^3$\\
\eqref{inc:completion-bad-pairs} & $6\cdot10^{11}B^{14}$\\
\eqref{inc:metsch-bound-one} & $3\cdot10^5B^6$\\
\eqref{inc:metsch-bound-two} & $3\cdot10^6B^8$\\
\eqref{inc:completion-clique-sizes} & $8000B^4$\\
\eqref{inc:completion-exact-cliques} & $6\cdot10^6B^8$\\
\eqref{inc:completion-restoration} & $4\cdot10^7B^8$\\
\eqref{inc:BM-bound} & $4\cdot10^{15}B^{16}$\\
\bottomrule
\end{tabular}
\end{center}
For the last row, with $f(a)=6a^4+9a^3+19a^2+8a$,
\[
 f(a_0)\le f(7129)B^{16}<1.6\cdot10^{16}B^{16}.
\]
Every threshold in the table is strictly below $10^{18}B^{16}$.
Finally, $K\le39B^2$ gives
$(K+2)^2\le1681B^4$ and
$K(K-1)+3B+2\le1526B^4$.
The degree, blocking-set, and remaining reinsertion conditions in
\eqref{stab:uniform-degree-range} and
\eqref{stab:uniform-reinsertion-range} follow directly from
$B\ge1$ and $q\ge10^{18}B^{16}$.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{stab:main}]
Write $B=b+1$ and $C=8b+10$.

\paragraph{Degree reduction.}
The numerical conditions used below are supplied by
Lemma~\ref{stab:uniform-completion-bounds}.
The automatic degree cap theorem applies because
$q\ge10^9B^8$.  The minimum-degree consequence of the linear-window
degree theorem gives $d_F(v)\ge q-b-2$.  Thus
\eqref{stab:degree-hypotheses} holds.

\paragraph{Large excess.}
Suppose $\sigma>q-C$.  Lemma~\ref{stab:sigma-dichotomy}
gives at least $q^2-10B$ full vertices.  Apply intrinsic recognition
(Theorem~\ref{inc:intrinsic-many-full-recognition}) with
$s=1$, $t=10B$.  Its conclusion is exactly $F\subseteq P-p$.
The first parameter choice in
\eqref{stab:uniform-parameter-choices} applies.

\paragraph{A polarity after deletion.}
Suppose $\sigma<C$.  Choose $S,F_0$ as in
Proposition~\ref{stab:deletions}.  Intrinsic recognition applies
using a prescribed clean full set $C_0$ of the size in
\eqref{stab:clean-full-count}, with parameters
\begin{equation}
 s=k+1=2B+2,\qquad t=t_0=2B^2+35B-2,
 \qquad K=s+t=2B^2+37B.
 \label{stab:incidence-parameters}
\end{equation}
Its construction supplies a polarity graph $P$ and a set $Q$ of
$s$ omitted points with $F_0\subseteq P-Q$.
It also supplies exact incidences at $C_0$ and
\begin{equation}
 |N_{F_0}(x)\cap C_0|\ge q+1-K
 \qquad(x\in V(F_0)).
 \label{stab:old-clean-neighbours}
\end{equation}
Every old polar line has at most $K$ points outside $C_0$.
Indeed, the $s$ missing lines contain no point of $C_0$, and their
union has at least $s(q+1)-\binom{s}{2}$ points.  At most $t$
further points lie outside $C_0$.  An old polar line meets the
missing-line union in at most $s$ points, giving the claimed bound.

\paragraph{Restoring vertices and their old neighbours.}
For each $v\in S$, put $B_v=N_F(v)\setminus S$.  These old vertices
avoid $C_0$, and
\begin{equation}
 |B_v|\ge q-b-2-(k-1)=q-3B-1.
 \label{stab:external-neighbours}
\end{equation}
The lines $\{\pi(x):x\in B_v\}$ meet pairwise outside $C_0$;
an intersection in $C_0$ would give a four-cycle in $F$.
The bounded-pencil lemma makes them concurrent at a point $p_v$
outside $C_0$.  This centre cannot be an old point $x$:
\eqref{stab:old-clean-neighbours} would supply at least $q+1-K$
further lines through $x$, indexed by points of $C_0$, disjoint
from the line indices in $B_v$. The combined number is at least
$(q-3B-1)+(q+1-K)=2q-3B-K>q+1$, by
\eqref{stab:uniform-reinsertion-range}. Thus $p_v\in Q$.
If two distinct deleted vertices had the same centre, their line
families would have at most one common member by $C_4$-freeness,
but would together have at least $2(q-3B-1)-1>q+1$ members.
The points $p_v$ are therefore distinct.  These assignments respect
every old--new edge.

\paragraph{Restoring edges between the deleted vertices.}
By the elementary even-order polarity
bound (Lemma~\ref{struct:even-polarity-bound}), $e(P)\le M$ and all
degrees of $P$ are at least $q$.  Hence
\[
 e(P-Q)\le M-sq+\binom{s}{2}.
\]
On the other hand,
\[
 e(F_0)=M-(k+1)q-k-b+\sum_{v\in S}\delta_v+e(F[S]).
\]
Consequently the number $D_0$ of old host edges absent from $F_0$
satisfies
\begin{equation}
 D_0\le k+b+\binom{k+1}{2}=2B^2+6B+1.
 \label{stab:missing-old-edges}
\end{equation}

Suppose $uv\in E(F[S])$ but $p_u,p_v$ are nonadjacent in $P$.
Write $\ell=\pi(p_u)$ and $j=\pi(p_v)$.
The rule $x\mapsto\pi(x)\cap j$ is a bijection from the points
of $\ell$ to those of $j$.  It is well defined because
$p_v\notin\ell$; if distinct points had the same image $y$,
the line $\pi(y)$ would contain both points and hence equal $\ell$,
forcing $y=p_u\notin j$, a contradiction.
Since $B_u\subseteq\ell$ and $B_v\subseteq j$, at least
$|B_u|+|B_v|-(q+1)$ of the matched pairs lie in $B_u\times B_v$.
At most one is a loop.  No nonloop edge occurs in both orientations,
because $|B_u\cap B_v|\le1$.
Thus there are at least
\[
 |B_u|+|B_v|-q-2\ge q-6B-4
\]
distinct old host edges between these two sets.  All are absent
from $F_0$, since an edge present there would make a four-cycle
with $uv$ in $F$.  This contradicts \eqref{stab:missing-old-edges}.
All edges inside $S$ are respected as well.  Since $|Q|=|S|+1$,
we have obtained a spanning embedding $F\subseteq P-p$.

\paragraph{Orthogonality and the exact deficit.}
For either branch, $e(P)\ge e(F)+d_P(p)\ge M-b$.
Lemma~\ref{stab:orthogonal-host} therefore makes the host orthogonal.
If $p$ is absolute, $e(P-p)=M-q=m_0$; otherwise
$e(P-p)=M-q-1=m_0-1$.
The asserted numbers of deleted edges follow by subtracting
$e(F)=m_0-b$.

\end{proof}

\begin{remark}[The quantitative range]
The bound is uniform in $b$ and $q$ subject to
$q\ge10^{18}(b+1)^{16}$.  In particular, it includes every fixed
edge deficit as $q$ tends to infinity.  The linear deficit range
$b$ proportional to $q$ remains beyond this estimate.
\end{remark}

% Source: sections/extremal_cores.tex
\section{Degree deficits at the extremal bound}
\label{sec:extremal-cores}

We now refine the structure of cores at the edge count $m_0$.
The local estimates in this section give a smaller threshold for
extremal recognition, unique completion at zero surplus, and
surplus gaps at smaller orders.
We use the deficit notation from Section~\ref{sec:counting}.
For a $C_4$-free graph on $n$ vertices, Lemma~\ref{lem:codegree-identities}
gives
\begin{equation}
 u_v=q\delta_v-1+a_v.
 \label{eq:core-local-deficit}
\end{equation}
Throughout, $H=\{v:d_F(v)=q+1\}$ and $L=\{v:d_F(v)\le q\}$.

\subsection{The weighted surplus and uncovered partners}

From now until the end of this section, unless otherwise stated,
$q\ge4$ is even and $F$ satisfies
\begin{equation}
 |V(F)|=q^2+q,\qquad e(F)=m_0,\qquad
 F\text{ is }C_4\text{-free},\qquad \Delta(F)\le q+1.
 \label{eq:core-working-hypotheses}
\end{equation}
Thus $V(F)=H\sqcup L$, all deficits are nonnegative, and
\[
 \sum_{v\in L}\delta_v=2q.
\]
For $v\in H$, put $s_v=a_v-2$, and define
\begin{equation}
 \eta=\sum_{v\in H}s_v,\qquad
 \omega=\sum_{v\in L}\delta_vd_L(v)
        =\sum_{uv\in E(F[L])}(\delta_u+\delta_v).
 \label{eq:core-surplus-definition}
\end{equation}
Lemma~\ref{lem:good-vertices} gives $s_v\ge0$.
As in that lemma, a vertex of $H$ is good when $s_v=0$.
Every good vertex $v$ has a unique uncovered partner $f(v)$,
and $vf(v)\in E(F)$.  A vertex of $H$ that is not good is called
bad.  Write $\mathcal B$ for the bad vertex set and $B_0=|\mathcal B|$.

\begin{lemma}[The weighted deficit identity]
\label{lem:core-weighted-budget}
Under \eqref{eq:core-working-hypotheses},
\begin{equation}
 \eta+\sum_{v\in L}(\delta_v-1)(\delta_v+2)+\omega=2q.
 \label{eq:core-weighted-budget}
\end{equation}
\end{lemma}

\begin{proof}
Put
\[
 \sigma=\sum_{v\in L}(\delta_v-1),\qquad
 \chi=\sum_{v\in L}\delta_v(\delta_v-1).
\]
Then $|L|=2q-\sigma$ and $|H|=q^2-q+\sigma$.
Weighted counting across $L,H$ gives
\[
 \sum_{v\in H}a_v
 =\sum_{w\in L}\delta_w
       \bigl(q+1-\delta_w-d_L(w)\bigr)
 =2q^2-\chi-\omega.
\]
Subtracting $2|H|$ gives
$\eta=2q-2\sigma-\chi-\omega$, which is
\eqref{eq:core-weighted-budget}.
\end{proof}

The good-vertex commutator \eqref{eq:good-commutator} has a useful
immediate consequence.  If $u,v$ are good and $f(u)=v$, then $v$
is the only good neighbour of $u$.  Since $a_u=2$, at most two
neighbours of $u$ lie in $L$.  Consequently
\begin{equation}
 \text{a good--good uncovered pair implies }
 |N_F(u)\cap\mathcal B|\ge q-2
 \text{ and }\eta\ge q-2.
 \label{eq:core-good-pair-cost}
\end{equation}

Suppose now that there is no uncovered pair consisting of two
good vertices.  Define
\[
 G_0=\{v\in H:v\text{ is good and }f(v)\in L\},\qquad
 D=H\setminus G_0,\qquad p=|D|,
\]
and put $X=f(G_0)\subseteq L$.  We call the vertices of $X$
active.  For $a\in X$, let
$Z_a=\{v\in G_0:f(v)=a\}$.

\begin{lemma}[Exceptional vertices and support pairs]
\label{lem:core-support}
With the preceding notation,
\begin{equation}
 p\le2\eta.
 \label{eq:core-exception-bound}
\end{equation}
Every vertex $v\in G_0$ has $f(v)$ as its only neighbour in $X$.
If $\delta_{f(v)}=1$, then $v$ has exactly one further low
neighbour, of deficit one, outside $X$.  No two such vertices
have the same pair of low neighbours.
If $\delta_{f(v)}=2$, then $f(v)$ is the only low neighbour of $v$.

In particular, writing $\ell_i=|\{v:\delta_v=i\}|$,
\begin{equation}
 |G_0|\le
 \left\lfloor\frac{\ell_1^2}{4}\right\rfloor+\ell_2(q-1).
 \label{eq:core-support-capacity}
\end{equation}
For every vertex $w$ of deficit two, with $Z_w=\varnothing$ if
$w\notin X$, one also has
\begin{equation}
 N_F(w)\cap G_0=Z_w,\qquad
 |Z_w|=q-1-d_L(w)-d_D(w).
 \label{eq:core-deficit-two-fibre}
\end{equation}
\end{lemma}

\begin{proof}
For a bad vertex $b$, its uncovered degree is $u_b=s_b+1$.
The number of its uncovered partners that are also neighbours
is odd, since its neighbourhood of order $q+1$ induces a matching
with an odd number of isolated vertices.
This number is at most $s_b$ if $s_b$ is odd, and at most
$s_b+1$ if $s_b$ is even.
Every good vertex in $D$ has a bad uncovered partner.
If $B_{\rm even}$ counts the bad vertices with even $s_b$, then
\[
 p\le B_0+\eta+B_{\rm even}\le2\eta,
\]
where the last inequality follows from
$B_0+B_{\rm even}\le\sum_{b\in\mathcal B}s_b=\eta$.

Let $v\in G_0$.  If $a\in X\setminus\{f(v)\}$ were another
neighbour of $v$, choose $x\in G_0$ with $f(x)=a$.
Equation \eqref{eq:good-commutator} would give
$xf(v)\in E(F)$, producing the four-cycle $f(v),v,a,x$.
Thus $f(v)$ is the only neighbour of $v$ in $X$.
The statements about the other low neighbours now follow from
$a_v=2$.  Two vertices with the same pair of low neighbours
would form a four-cycle with that pair.

The vertices whose partner has deficit one therefore correspond
injectively to pairs consisting of a deficit-one point of $X$
and a deficit-one point of $L\setminus X$.  Their number is at
most $\lfloor\ell_1^2/4\rfloor$.
A deficit-two point has degree $q-1$, so it can be the partner
of at most $q-1$ vertices of $G_0$.
No point of larger deficit is adjacent to a good vertex.
This proves \eqref{eq:core-support-capacity}.
Finally, if a deficit-two point $w$ is adjacent to $v\in G_0$,
then $a_v=2$ makes $w$ the only low neighbour of $v$, hence
$f(v)=w$.  Partitioning $N_F(w)$ into $L,G_0,D$ proves
\eqref{eq:core-deficit-two-fibre}.
\end{proof}

\begin{lemma}[Localizing the bad partners]
\label{lem:core-bad-partners}
Assume that there is no good--good uncovered pair.
Let $K\subseteq\mathcal B$ be the set of bad vertices that have
a good vertex of $H$ as an uncovered partner, and put $k=|K|$.
Then
\begin{align}
 d_{G_0}(b)&\le2 &&(b\in K), \label{eq:core-partner-localization}\\
 p&\le\eta+2k,\qquad p\le2\eta+k-B_0,
 \label{eq:core-partner-capacity}\\
 \eta&\ge\frac{kq}{k+1}-2k.
 \label{eq:core-partner-surplus}
\end{align}
Every member of $K$ has at least $q-1$ neighbours in $D\cup L$.
If a member of $K$ has at least two good uncovered partners in
$H$, then it has no neighbour in $G_0$.
\end{lemma}

\begin{proof}
Fix $b\in K$, and choose a good vertex $x\in H$ with $f(x)=b$.
For every $v\in G_0$, equation \eqref{eq:good-commutator} gives
\begin{equation}
 A_{b,v}=A_{x,f(v)}.
 \label{eq:core-partner-row}
\end{equation}
If $a\in X\cap N_F(x)$, then every member of $Z_a$ is adjacent
to both $a$ and $b$.  Thus $|Z_a|\le1$.
Since $a_x=2$, there are at most two low neighbours of $x$,
proving \eqref{eq:core-partner-localization}.

For $b\in K$, let $g_b$ count the good vertices of $H$ whose
uncovered partner is $b$.  The absence of a good--good uncovered
pair gives
\[
 p=B_0+\sum_{b\in K}g_b.
\]
Since $g_b\le s_b+1$ and every bad vertex outside $K$
contributes at least one to $\eta$,
\[
 p\le B_0+\sum_{b\in K}(s_b+1)\le\eta+2k.
\]
Let $k_{\rm even}$ count the members of $K$ with even $s_b$.
The parity argument in Lemma~\ref{lem:core-support} gives
$g_b\le s_b$ for odd $s_b$, and $g_b\le s_b+1$ for even $s_b$.
Therefore
\[
 p\le B_0+\sum_{b\in K}s_b+k_{\rm even}
 \le\eta+k+k_{\rm even}.
\]
Also
$k_{\rm even}\le\sum_{b\in\mathcal B}(s_b-1)=\eta-B_0$,
which proves the second bound in \eqref{eq:core-partner-capacity}.

For $b\in K$, at most $p-1$ neighbours lie in $D$ and at most
two lie in $G_0$.  Hence $d_L(b)\ge q-p$ and
$s_b=a_b-2\ge q-p-2$.
Summing over $K$ and using $p\le\eta+2k$ gives
\[
 \eta\ge k(q-p-2)\ge k(q-\eta-2k-2),
\]
which rearranges to \eqref{eq:core-partner-surplus}.

For the last assertion, suppose that $x_1,x_2$ are two good
uncovered partners of $b$ and that $v\in G_0\cap N_F(b)$.
Putting $a=f(v)$ in \eqref{eq:core-partner-row} shows that
both $x_1a$ and $x_2a$ are edges.  Both $x_1,x_2$ are also
adjacent to $b$, producing the four-cycle $b,x_1,a,x_2$.
\end{proof}

\subsection{The minimum degree of an extremal core}

For $q\ge6$, the degree-sequence restriction of Firke, Kosek, Nash and
Williford \cite[Theorem~3]{FirkeEtAl2013} gives degrees between
$q-2$ and $q+1$ under \eqref{eq:core-working-hypotheses}, with at most
one vertex of degree $q-2$.
Corollary~\ref{cor:core-individual-deficit} gives this initial lower
bound independently and strengthens it to $q-1$ when $q=4$.
The next theorem excludes degree $q-2$ throughout.

\begin{theorem}[Minimum degree]
\label{thm:minimum-degree}
\label{thm:core-min}
Let $q\ge4$ be even.  Every graph satisfying
\eqref{eq:core-working-hypotheses} has
\[
 d_F(v)\in\{q-1,q,q+1\}\qquad(v\in V(F)).
\]
\end{theorem}

\begin{proof}
Corollary~\ref{cor:core-individual-deficit} gives
$\delta_v\le3$ for every vertex, and already gives
$\delta_v\le2$ for $q\le10$.
It remains to exclude deficit three when $q\ge12$.

First, there is at most one vertex of deficit three.
Indeed, let $W_3=\{v:\delta_v=3\}$, let $r=|W_3|$, and put
$J_3=\sum_{w\in W_3}d_L(w)$.
If a full-degree vertex has $j\ge1$ neighbours in $W_3$, its
surplus is at least $3j-2\ge j$.
Consequently
\[
 \eta\ge e_F(W_3,H)=r(q-2)-J_3,\qquad \omega\ge3J_3.
\]
The weighted budget therefore gives
\[
 2q\ge\eta+10r+\omega\ge r(q+8)+2J_3,
\]
which is impossible for $r\ge2$.
Suppose henceforth that $w$ is the unique deficit-three vertex.

We claim that there is no good--good uncovered pair.
Suppose that $u,v$ are such a pair.  By
\eqref{eq:core-good-pair-cost}, $u$ has at least $q-2$ bad
full-degree neighbours.
Put $j=d_L(w)$ and $r_w=d_H(w)=q-2-j$.
All full-degree neighbours of $w$ are bad, and their set
intersects $N_F(u)\cap\mathcal B$ in at most one point.
Thus $\eta\ge q+r_w-3$.
Every edge of $F[L]$ incident with $w$ contributes at least four
to $\omega$, so
\[
 2q\ge\eta+10+\omega
 \ge q+r_w-3+10+4(q-2-r_w)
 =5q-1-3r_w\ge2q+5,
\]
a contradiction.
We may consequently use $G_0,D,p,K,k$ from
Lemmas~\ref{lem:core-support} and \ref{lem:core-bad-partners}.

Let $t$ be the number of deficit-two vertices.
The deficit sum gives
\[
 |L|=2q-t-2,\qquad |H|=q^2-q+t+2,\qquad
 \ell_1=2q-2t-3.
\]
In particular, $0\le t\le q-2$.
By the support-pair bound,
\[
 q^2-q+t+2-p
 \le(q-t-1)(q-t-2)+t(q-1),
\]
and hence
\begin{equation}
 p\ge2q+t(q-t-1).
 \label{eq:core-deficit-three-capacity}
\end{equation}
The weighted budget is
\begin{equation}
 \eta+4t+10+\omega=2q.
 \label{eq:core-deficit-three-budget}
\end{equation}
Since $p\le2\eta$, equation \eqref{eq:core-deficit-three-capacity}
implies $\eta\ge q$.

Put $T_0=D\cup L$.
Equations \eqref{eq:core-exception-bound} and
\eqref{eq:core-deficit-three-budget} give
\[
 |T_0|\le2\eta+|L|\le6q-22-9t.
\]
Every member of $K$ has at least $q-1$ neighbours in $T_0$.
Any two such neighbourhoods intersect in at most one point.
Thus, for any $K'\subseteq K$,
\begin{equation}
 |T_0|\ge |K'|(q-1)-\binom{|K'|}{2}.
 \label{eq:core-partner-union}
\end{equation}
Seven members would give
$|T_0|\ge7q-28>6q-22-9t$, so $k\le6$.
It follows that
$p\le\eta+12\le2q+2-4t$.
Combining this with \eqref{eq:core-deficit-three-capacity} yields
\[
 t(q-t+3)\le2.
\]
If $t\ge1$, then $t\le q-2$ makes the left side at least five.
Therefore $t=0$.

We now have
\begin{equation}
 p\ge2q,\qquad q\le\eta\le2q-10,\qquad
 |T_0|\le\eta+2k+2q-2\le4q-12+2k.
 \label{eq:core-deficit-three-final-bounds}
\end{equation}
If $k=6$, equation \eqref{eq:core-partner-union} gives
$6q-21\le|T_0|\le4q$, impossible for $q\ge12$.
If $k=5$ and $q\ge14$, it gives
$5q-15\le|T_0|\le4q-2$, again impossible.
Thus, for $q\ge14$, one has $k\le4$, whence
\[
 2q\le p\le\eta+8\le2q-2.
\]

Only $q=12$ remains.
By \eqref{eq:core-deficit-three-final-bounds},
$12\le\eta\le14$ and $\omega=14-\eta\le2$.
Since every low--low edge incident with $w$ contributes at least
four to $\omega$, one has $d_L(w)=0$.
All ten neighbours of $w$ are therefore bad full-degree vertices,
so $B_0\ge10$.
The preceding six-vertex argument gives $k\le5$, and the sharper
bound in \eqref{eq:core-partner-capacity} yields
\[
 p\le2\eta+k-B_0\le28+5-10=23<24,
\]
contrary to $p\ge2q$.
\end{proof}

\subsection{Deficit two and the zero-surplus case}

The next capacity alternative will be used both to recognize the
zero-surplus case and to prove the quantitative gap.

\begin{lemma}[A capacity alternative for deficit two]
\label{lem:core-deficit-two-alternative}
Suppose that $F$ satisfies \eqref{eq:core-working-hypotheses} and has
no good--good uncovered pair.  If a vertex of deficit two exists,
then at least one of
\begin{equation}
 2p\ge q,\qquad 3p-\eta\ge q+1
 \label{eq:core-deficit-two-alternative}
\end{equation}
holds.
\end{lemma}

\begin{proof}
By Theorem~\ref{thm:minimum-degree}, all positive deficits are
one or two.
Let $t\ge1$ count the deficit-two vertices.  Then
\[
 |H|=q^2-q+t,\qquad \ell_1=2q-2t,
 \qquad \eta+4t+\omega=2q.
\]
Equation \eqref{eq:core-support-capacity} gives
\[
 p\ge(t-1)q-t(t-2).
\]
For $2\le t\le q$, this concave quadratic is at least $q$:
its values at $t=2$ and $t=q$ are both $q$.
Thus the first alternative in
\eqref{eq:core-deficit-two-alternative} holds whenever $t\ge2$.

It remains to consider a unique deficit-two vertex $w$.
Put $J_w=d_L(w)$ and $n_D=d_D(w)$.
If $w$ is inactive, equation \eqref{eq:core-deficit-two-fibre}
gives $J_w=q-1-n_D\ge q-1-p$.
Its low--low edges contribute at least $3J_w$ to $\omega$.
The budget therefore yields
\[
 2q\ge\eta+4+3(q-1-p),
 \qquad 3p-\eta\ge q+1.
\]

Suppose instead that $w$ is active, and write $Z=Z_w$.
Every vertex of $G_0\setminus Z$ is represented by a pair of
deficit-one low neighbours, one active and one inactive.
There are $2q-2$ deficit-one vertices, so
\[
 q^2-q+1-p=|G_0|
 \le(q-1)^2+|Z|
 =(q-1)^2+q-1-J_w-n_D.
\]
Hence
\begin{equation}
 J_w+n_D\le p-1.
 \label{eq:core-single-fibre-capacity}
\end{equation}
The set $Z$ is independent: an edge between two of its vertices
would give one of them a common neighbour with its uncovered
partner $w$.
Each member of $Z$ has $w$ as its only low neighbour and has
$q$ full-degree neighbours.
Among its neighbours in $G_0\setminus Z$, at most one can use
any given active low point and at most one can use any given
inactive low point, by $C_4$-freeness.
The two sets of deficit-one points have total size $2q-2$.
Thus at most $q-1$ of its neighbours lie in $G_0$, and it has
at least one neighbour in $D$.

Every member of $D$ has at most one neighbour in $Z$, because
all vertices of $Z$ are adjacent to $w$.
Moreover a member of $D$ adjacent to $w$ has no neighbour in
$Z$, because $w$ is the uncovered partner of every vertex of
$Z$.
Consequently $|Z|+n_D\le p$.
Together with \eqref{eq:core-single-fibre-capacity}, this gives
\[
 q-1=J_w+|Z|+n_D\le J_w+p\le2p-1,
\]
and hence $2p\ge q$.
\end{proof}

\begin{theorem}[Zero surplus and unique polarity completion]
\label{thm:zero-surplus-completion}
Let $F$ satisfy \eqref{eq:core-working-hypotheses}.  If $\eta=0$, then
all its degrees belong to $\{q,q+1\}$, and there is a partition
\[
 L=X\sqcup Y,\qquad |X|=|Y|=q,
\]
with a vertex $c\in Y$ such that the following hold.
\begin{enumerate}
\item The graph $F[L]$ is the star with centre $c$ and leaf set
      $X$, together with $q-1$ isolated vertices.
\item Every vertex of $H$ has one neighbour in $X$ and one in
      $Y\setminus\{c\}$.  Each pair in
      $X\times(Y\setminus\{c\})$ is the neighbourhood in $L$ of
      exactly one vertex of $H$.
\item Adjoining a new vertex $p$ with neighbourhood $Y$ gives a
      $C_4$-free graph $\widehat F$ on $q^2+q+1$ vertices with
      $M$ edges.  If $\widehat A$ is its adjacency matrix and
      $D_{\mathcal A}$ is the diagonal indicator matrix of
      $\mathcal A=X\cup\{p\}$, then
      \begin{equation}
       B=\widehat A+D_{\mathcal A}
       \quad\text{satisfies}\quad B^2=qI+J.
       \label{eq:core-completion-design}
      \end{equation}
\end{enumerate}
The matrix $B$ defines a projective plane of order $q$ and a
polarity with exactly $q+1$ absolute points, namely
$\mathcal A$.  In particular, $F$ is obtained by deleting an
absolute point from its polarity graph.
The one-point polarity completion is unique on the labelled
vertex set $V(F)\cup\{p\}$.
\end{theorem}

\begin{proof}
Since $\eta=0$, every vertex of $H$ is good.
Equation \eqref{eq:core-good-pair-cost} excludes a good--good
uncovered pair, and \eqref{eq:core-exception-bound} gives $D=\varnothing$.
Lemma~\ref{lem:core-deficit-two-alternative} excludes deficit two.
Theorem~\ref{thm:minimum-degree} therefore shows that every
positive deficit is one.
It follows that
\[
 |L|=2q,\qquad |H|=q(q-1),\qquad
 \eta=2\bigl(q-e(F[L])\bigr)=0.
\]
Thus $F[L]$ has $q$ edges and every vertex of $H$ has exactly
two low neighbours.

All full-degree vertices belong to $G_0$.
Put $X=f(H)$ and $Y=L\setminus X$.
By Lemma~\ref{lem:core-support}, every vertex of $H$ has one
neighbour in each of $X,Y$, and no pair is repeated.
Let $T_*$ be the resulting simple bipartite support graph on
$X,Y$: its $q(q-1)$ edges correspond to the vertices of $H$.
Write $J_*=F[L]$ and $j_v=d_{J_*}(v)$.
For every $v\in L$,
\begin{equation}
 d_{T_*}(v)=d_H(v)=q-j_v.
 \label{eq:core-support-degrees}
\end{equation}

For $a\in X$, the full-degree vertices uncovered from $a$ are
exactly the $d_{T_*}(a)$ members of its fibre.
Equation \eqref{eq:core-local-deficit} shows that $a$ has
$q-1+j_a$ uncovered partners in total, hence exactly $2j_a-1$
uncovered partners in $L$.
This number is nonnegative, so $j_a\ge1$ and
$d_{T_*}(a)\le q-1$.
Since vertices of $Y$ have support degree at most $q$,
\[
 |X|\ge q,\qquad |Y|\ge q-1.
\]
As $|X|+|Y|=2q$, only
\begin{equation}
 (|X|,|Y|)=(q,q)\quad\text{or}\quad(q+1,q-1)
 \label{eq:core-support-part-sizes}
\end{equation}
is possible.

We need the following identity in the low-degree graph:
\begin{equation}
 \sum_{b\in N_{J_*}(a)}j_b=q\qquad(a\in X).
 \label{eq:core-active-low-identity}
\end{equation}
Indeed, precisely $2q-2j_a$ points of $L\setminus\{a\}$ are
covered from $a$.
Of these, $q-j_a$ have their common neighbour with $a$ in $H$,
one for each support edge at $a$.
The others are counted by
$\sum_{b\in N_{J_*}(a)}(j_b-1)$.
There are no repetitions or overlaps, by $C_4$-freeness.
Rearrangement proves \eqref{eq:core-active-low-identity}.

Suppose first that $(|X|,|Y|)=(q+1,q-1)$.
Every vertex of $Y$ has support degree $q$, so $j_y=0$.
All $q$ edges of $J_*$ then lie in $X$, and every vertex of
$X$ has positive $J_*$-degree.
The graph $J_*[X]$ has $q+1$ vertices and $q$ edges, so it has
a tree component; otherwise each component would have at
least as many edges as vertices.
This component is nontrivial and has a leaf $a$.
By \eqref{eq:core-active-low-identity}, its unique neighbour
has $J_*$-degree $q$, hence support degree zero.
This contradicts its membership in $X=f(H)$.

Thus $|X|=|Y|=q$.
Every point of $X$ attains the support-degree bound $q-1$,
and so has $J_*$-degree one.
If $c$ is the unique low neighbour of a point of $X$,
\eqref{eq:core-active-low-identity} gives $j_c=q$.
Since $J_*$ has exactly $q$ edges, all its edges are incident
with $c$.
The point $c$ lies in $Y$, and the $q$ points of $X$ are
exactly the leaves of this star.
All other points of $Y$ are isolated in $J_*$.
Equation \eqref{eq:core-support-degrees} now gives
\[
 T_*=K_{X,Y\setminus\{c\}}.
\]
This proves the first two assertions.

Every pair of distinct vertices of $Y$ is uncovered in $F$.
A full-degree vertex has only one neighbour in $Y$, and the
star description of $J_*$ excludes a common neighbour in $L$.
Adjoining $p$ with neighbourhood $Y$ therefore preserves
$C_4$-freeness.
The resulting graph has $M$ edges; its degree-$q$ vertices are
exactly $\mathcal A=X\cup\{p\}$, while all others have degree
$q+1$.

The set $\mathcal A$ is independent, and every edge incident
with $\mathcal A$ has codegree zero.
For an edge $av$ with $a\in X$ and $v\in H$, this follows
from $f(v)=a$; adding $p$ does not change that codegree.
The star edges $ac$ have codegree zero, as do the edges $py$
because $Y$ is independent.
The total number of uncovered pairs in $\widehat F$ is
\[
 \binom{q^2+q+1}{2}
 -q^2\binom{q+1}{2}-(q+1)\binom q2=q(q+1).
\]
This equals the number of edges incident with $\mathcal A$.
Every other pair of distinct vertices consequently has
codegree one.
Adding a diagonal one at each point of $\mathcal A$ changes
the off-diagonal entries of $\widehat A^2$ precisely at those
incident edges, and gives diagonal entries $q+1$.
This proves \eqref{eq:core-completion-design}.

The rows and columns of $B$ have size $q+1$, and any two
distinct rows or columns meet in exactly one position.
They define a projective plane of order $q$.
Symmetry gives a polarity by exchanging the point and line
with the same index.
Its absolute points are exactly the diagonal ones of $B$,
namely $\mathcal A$.
The row indexed by $c$ is exactly $\mathcal A$, so the
absolute points lie on the line indexed by $c$.

For uniqueness, the uncovered-pair graph of $F$ consists
exactly of
\begin{equation}
 K_Y,\qquad \{ca:a\in X\},\qquad \{vf(v):v\in H\}.
 \label{eq:core-uncovered-structure}
\end{equation}
Pairs within $X$ are covered by $c$, pairs in
$X\times(Y\setminus\{c\})$ are covered by their support
vertex, and every vertex of $H$ has its unique uncovered
partner in $X$; this proves \eqref{eq:core-uncovered-structure}.
A neighbourhood for a new vertex preserves $C_4$-freeness
exactly when it is a clique in this uncovered-pair graph.
Every clique of size at least three is contained in $Y$:
vertices of $H$ have uncovered degree one, and a vertex of
$X$ has only $c$ as an uncovered partner in $L$.
Thus there is a unique $C_4$-free extension in which the new
vertex has degree $q$, namely $N(p)=Y$, and no such extension
has a larger degree.
Every vertex of a polarity graph of a plane of order $q$
has degree $q$ or $q+1$.
Any one-point polarity completion is therefore this extension,
with the new point absolute.  Its incidence matrix is then
determined by its adjacency matrix and its degree-$q$ vertices,
proving the asserted uniqueness.
\end{proof}

\subsection{The gap for two-valued degree sequences}

We next give a quantitative version of the low-star criterion.
Its square identity also records the interaction between
surplus and uncovered pairs.

\begin{theorem}[The two-degree gap]
\label{thm:two-degree-gap}
Let $F$ satisfy \eqref{eq:core-working-hypotheses}, and suppose that all
its degrees belong to $\{q,q+1\}$.
Write
\[
 t=e(F[L]),\qquad \kappa=q-t.
\]
Then $t\le q$, $\eta=2\kappa$, and
\begin{equation}
 \kappa=0\quad\text{or}\quad
 \kappa\ge\left\lceil\frac{2q-11}{5}\right\rceil.
 \label{eq:core-two-degree-gap}
\end{equation}
Consequently, either condition
\[
 e(F[L])=q
 \qquad\text{or}\qquad
 e(F[L])>\frac{3q+11}{5}
\]
forces the unique polarity completion in
Theorem~\ref{thm:zero-surplus-completion}.
\end{theorem}

\begin{proof}
The degree sum gives $|L|=2q$ and $|H|=q(q-1)$.
The weighted budget reduces to
\[
 \eta+2e(F[L])=2q,
\]
so $t\le q$ and $\eta=2\kappa$.
Put $h_0=q(q-1)$ and $r_v=d_L(v)$ for $v\in L$.
Let $u_{HH},u_{LL},u_{HL}$ count uncovered unordered pairs
of the indicated types.
Summing \eqref{eq:core-local-deficit} over the two parts gives
\[
 2u_{HH}+u_{HL}=h_0+2\kappa,\qquad
 2u_{LL}+u_{HL}=2q(q-1)+2t=2q^2-2\kappa.
\]
Hence
\[
 2u_{LL}=q^2+q-4\kappa+2u_{HH}.
\]
Counting covered pairs in $L$ by their unique common neighbour
gives
\begin{align*}
 \binom{2q}{2}-u_{LL}
 &=\sum_{v\in L}\binom{r_v}{2}
   +\sum_{v\in H}\binom{2+s_v}{2}\\
 &=\frac12\sum_{v\in L}r_v^2+h_0-q+5\kappa
   +\sum_{v\in H}\binom{s_v}{2}.
\end{align*}
Substitution yields the identity
\begin{equation}
 \sum_{v\in L}r_v^2
 +2\sum_{v\in H}\binom{s_v}{2}
 +2u_{HH}=q^2+q-6\kappa.
 \label{eq:core-square-identity}
\end{equation}

If a good--good uncovered pair exists,
\eqref{eq:core-good-pair-cost} gives
\[
 \kappa\ge\frac{q-2}{2}>\frac{2q-11}{5},
\]
as required.
Otherwise every uncovered pair within $H$ has a bad endpoint.
Since $u_v=s_v+1$ for $v\in H$,
\[
 u_{HH}\le\sum_{v\in\mathcal B}u_v
 =B_0+2\kappa\le4\kappa.
\]
A graph with $t$ edges satisfies $\sum_v d(v)^2\le t(t+1)$.
Indeed, for every edge $uv$ the incident edge sets have union
of size $d(u)+d(v)-1\le t$, and summing
$d(u)+d(v)\le t+1$ over the edges proves the assertion.
Also $\sum_{v\in H}s_v=2\kappa$ gives
\[
 \sum_{v\in H}\binom{s_v}{2}\le\binom{2\kappa}{2}.
\]
Using these bounds in \eqref{eq:core-square-identity}, we obtain
\begin{align*}
 \kappa(2q-5-\kappa)
 &=q^2+q-6\kappa-(q-\kappa)(q-\kappa+1)\\
 &\le2u_{HH}+2\sum_{v\in H}\binom{s_v}{2}\\
 &\le8\kappa+2\binom{2\kappa}{2}
 =6\kappa+4\kappa^2.
\end{align*}
If $\kappa>0$, division gives $5\kappa\ge2q-11$.
This proves \eqref{eq:core-two-degree-gap}.
The stated recognition conditions force $\kappa=0$ and
therefore $\eta=0$.
\end{proof}

\subsection{A gap for the weighted surplus}

The support and partner estimates give a quantitative separation
between zero and positive surplus.

\begin{theorem}[The surplus gap]
\label{thm:surplus-gap}
\label{thm:core-gap}
Let $q\ge16$ be even, and let $F$ satisfy
\eqref{eq:core-working-hypotheses}.  Then
\begin{equation}
 \eta=0\quad\text{or}\quad\eta\ge\frac q2-2.
 \label{eq:core-surplus-gap}
\end{equation}
If $F$ has a vertex of degree $q-1$, then the second alternative
holds.  In particular, $\eta<q/2-2$ forces the unique
absolute-point polarity completion of
Theorem~\ref{thm:zero-surplus-completion}.
\end{theorem}

\begin{proof}
Suppose $\eta<q/2-2$.
Equation \eqref{eq:core-good-pair-cost} excludes a good--good
uncovered pair, so the notation and bounds of
Lemmas~\ref{lem:core-support} and \ref{lem:core-bad-partners}
apply.
Since $|L|\le2q$ and $p\le2\eta$,
\[
 |D\cup L|\le2\eta+2q<3q-4.
\]
Four members of $K$ would have at least
$4(q-1)-\binom42=4q-10$ distinct neighbours in this set.
This is impossible for $q\ge16$, so $k\le3$.
For $k=1,2,3$, the lower bounds in
\eqref{eq:core-partner-surplus} are
\[
 \frac q2-2,\qquad \frac{2q}{3}-4,\qquad
 \frac{3q}{4}-6,
\]
respectively.
All are at least $q/2-2$ when $q\ge16$.
Hence $k=0$, and every good full-degree vertex belongs to
$G_0$.  Thus $D=\mathcal B$ and $p\le\eta$.

Theorem~\ref{thm:minimum-degree} leaves only deficits one and two.
If a deficit-two vertex existed,
Lemma~\ref{lem:core-deficit-two-alternative} would give either
$2p\ge q$ or $3p-\eta\ge q+1$.
But
\[
 2p\le2\eta<q-4,\qquad
 3p-\eta\le2\eta<q-4,
\]
contradicting both alternatives.
All positive deficits therefore equal one.
By Theorem~\ref{thm:two-degree-gap}, either $\eta=0$ or
\[
 \eta\ge2\left\lceil\frac{2q-11}{5}\right\rceil
 \ge\frac q2-2,
\]
where the last inequality holds for $q\ge16$.
Thus $\eta=0$.
The remaining assertions follow from
Theorem~\ref{thm:zero-surplus-completion}.
\end{proof}

\subsection{An unrestricted degree conclusion}

\begin{corollary}[Unrestricted degree control for extremal cores]
\label{struct:unrestricted-extremal-degrees}
For every even $q\ge10^9$, every $C_4$-free graph $F$
on $q^2+q$ vertices with $m_0$ edges satisfies
\[
 d_F(v)\in\{q-1,q,q+1\}\qquad(v\in V(F)).
\]
Moreover, with
\[
 \delta_v=q+1-d_F(v),\quad
 H=\{v:d_F(v)=q+1\},\quad
 \eta(F)=\sum_{v\in H}\left(\sum_{w\in N_F(v)}\delta_w-2\right),
\]
one has $\eta(F)=0$ or $\eta(F)\ge q/2-2$.
In the zero case, $F$ has the unique absolute-point polarity
completion already proved for capped cores.
\end{corollary}

\begin{proof}
Apply Theorem~\ref{struct:automatic-fixed-deficit-cap} with $b=0$,
then Theorems~\ref{thm:core-min},~\ref{thm:core-gap},
and~\ref{thm:zero-surplus-completion}.
\end{proof}

% Source: sections/extremal_recognition.tex
\section{Graphs attaining the extremal bound}
\label{struct:extremal-core-recognition-section}

Write
\[
 N=q^2+q+1,\qquad n=N-1,\qquad
 M=\frac12q(q+1)^2,\qquad m_0=M-q.
\]
At zero edge deficit, concentration in two vertices gives the
sufficient threshold $q\ge10^{15}$, and the resulting recognition
theorem determines the missing absolute point uniquely.
The classification statement was announced by Firke, Kosek, Nash,
and Williford \cite[Theorem~2]{FirkeEtAl2013}, who stated that its
proof would appear in subsequent work.  The argument below derives
this classification and the unique completion from the degree and
incidence-completion results.

We first assume that $q\ge10$ is even and that $F$ is a $C_4$-free
graph satisfying
\begin{equation}
 |V(F)|=q^2+q,\qquad e(F)=m_0,\qquad
 q-1\le d_F(v)\le q+1\quad(v\in V(F)).
 \label{struct:core-three-degrees}
\end{equation}
Theorems~\ref{struct:automatic-fixed-deficit-cap} and~\ref{thm:core-min}
will remove both degree hypotheses in the final result.
Put
\[
 \delta_v=q+1-d_F(v),\quad
 H=\{v:\delta_v=0\},\quad L=\{v:\delta_v>0\},\quad
 Z=\{v:\delta_v=2\},\quad t=|Z|.
\]
For every vertex write
\[
 a_v=\sum_{w\in N_F(v)}\delta_w,\qquad
 r_v=|N_F(v)\cap L|,
\]
and let $u_v$ be the number of other vertices having no common
neighbour with $v$.  For subsets $I,J$ of the partition $V(F)=L\sqcup H$,
write $u_{IJ}$ for the number of uncovered unordered pairs of the
indicated type.  In particular $u_{HH}$ counts unordered pairs, not
the sum of their degrees.

The degree sum and the exact local path count give
\begin{align}
 \sum_{v\in L}\delta_v&=2q,&
 |L|&=2q-t,& |H|&=q^2-q+t,
 \label{struct:core-part-sizes}\\
 u_v&=q\delta_v-1+a_v.
 \label{struct:core-local-count}
\end{align}
At every vertex of $H$, the neighbourhood has odd order $q+1$ and
induces a matching with isolated vertices.  Thus $u_v\ge1$ and
$a_v\ge2$.  Set
\[
 s_v=a_v-2\quad(v\in H),\qquad
 \eta=\sum_{v\in H}s_v,\qquad
 \omega=\sum_{v\in L}\delta_vr_v.
\]
Weighted counting of the edges between $L$ and $H$ gives the exact
budget
\begin{equation}
 \eta+4t+\omega=2q.
 \label{struct:core-budget}
\end{equation}
Indeed,
\[
 2|H|+\eta
 =\sum_{v\in L}\delta_v(q+1-\delta_v-r_v)
 =2q^2-2t-\omega,
\]
which is equivalent to \eqref{struct:core-budget}.

\subsection{A bounded number of vertices of deficit two}

A full-degree vertex is called good when $s_v=0$, and bad otherwise.
Write $\mathcal B$ for the bad set and $B_0=|\mathcal B|$.
A good vertex has precisely one uncovered partner, denoted by $f(v)$;
neighbourhood parity also gives $vf(v)\in E(F)$.

For clarity, the commutation relation used below follows directly from
the $C_4$-free hypothesis.  Let $A$ be the adjacency matrix and $U$ the
zero-diagonal uncovered-pair matrix.  Then
\[
 A^2=qI+J-U-\operatorname{diag}(\delta_v),
\]
and therefore
\begin{equation}
 (AU-UA)_{uv}=(\delta_v-\delta_u)(1-A_{uv}).
 \label{struct:core-commutator}
\end{equation}
For good vertices $u,v$, this becomes
\begin{equation}
 A_{u,f(v)}=A_{f(u),v}.
 \label{struct:core-good-commutator}
\end{equation}

\begin{lemma}[The good--good pairs and the exceptional capacity]
\label{struct:core-exceptional-capacity}
Under \eqref{struct:core-three-degrees}, at most one uncovered pair
consists of two good vertices.  Consequently
\begin{equation}
 u_{HH}\le2\eta+1.
 \label{struct:core-full-holes}
\end{equation}
Define
\[
 G_0=\{v\in H:v\text{ is good and }f(v)\in L\},\qquad
 D=H\setminus G_0,\qquad p=|D|.
\]
Then
\begin{equation}
 p\le2\eta+2,
 \qquad
 |G_0|\le(q-t)^2+t(q-1).
 \label{struct:core-exceptional-and-support}
\end{equation}
In particular,
\begin{equation}
 t\le4.
 \label{struct:core-at-most-four}
\end{equation}
\end{lemma}

\begin{proof}
Suppose $u,v$ are good and $f(u)=v$.  If $w\ne v$ were another good
neighbour of $u$, then \eqref{struct:core-good-commutator}, applied to
$v,w$, would give $vf(w)\in E(F)$.  The four distinct vertices
$u,v,f(w),w$ would form a four-cycle.  Distinctness follows from the
uniqueness of the uncovered partners at $u$ and $v$.
Thus $v$ is the only good neighbour of $u$.
Since $a_u=2$, at most two neighbours of $u$ lie in $L$, even when
one of them has deficit two.  Hence $u$ has at least $q-2$ bad full
neighbours.

If three good vertices participated in good--good uncovered pairs,
their bad-neighbour sets would have union of size at least
$3(q-2)-3=3q-9$: each pair of such neighbourhoods intersects in at
most one vertex.  This is impossible because
$B_0\le\eta\le2q$ and $q\ge10$.
At most two good vertices therefore participate, giving at most one
such pair.  Every other uncovered $H$--$H$ pair touches $\mathcal B$,
so
\[
 u_{HH}\le1+\sum_{b\in\mathcal B}u_b
 =1+\eta+B_0\le2\eta+1.
\]

For each bad vertex $b$, the number of uncovered partners that are
also adjacent to $b$ is odd, because it equals the number of isolated
vertices in the matching induced by $N_F(b)$.
As $u_b=s_b+1$, this number is at most $s_b$ when $s_b$ is odd and
at most $s_b+1$ when $s_b$ is even.
Every good vertex in $D$ either has a bad partner or belongs to the
one possible good--good pair.  If $B_{\rm even}$ denotes the number
of bad vertices with even $s_b$, it follows that
\[
 p\le B_0+\eta+B_{\rm even}+2\le2\eta+2.
\]
The final inequality uses
$B_0+B_{\rm even}\le\sum_{b\in\mathcal B}s_b=\eta$.

Put $X=f(G_0)\subseteq L$.  For $v\in G_0$, its only neighbour in
$X$ is $f(v)$.  Indeed, if $a\in X\setminus\{f(v)\}$ were another
neighbour, choose $x\in G_0$ with $f(x)=a$.
Equation~\eqref{struct:core-good-commutator} gives $xf(v)\in E(F)$,
and $f(v),v,a,x$ form a four-cycle.
If $\delta_{f(v)}=1$, the equality $a_v=2$ says that $v$ has exactly
one further low neighbour, also of deficit one, in $L\setminus X$.
No two vertices of $G_0$ have the same pair of low neighbours.
There are $2q-2t$ vertices of deficit one, so these pairs number at
most $(q-t)^2$.  If $\delta_{f(v)}=2$, then $f(v)$ is the only low
neighbour of $v$; each such partner has degree $q-1$ and supports at
most $q-1$ vertices.  This proves the second assertion in
\eqref{struct:core-exceptional-and-support}.

Since $|H|=q^2-q+t$, we obtain
\[
 p\ge(t-1)q-t(t-2).
\]
Together with $p\le2\eta+2$ and \eqref{struct:core-budget}, this gives
\begin{equation}
 (t-5)q-t^2+10t-2\le0.
 \label{struct:core-t-quadratic}
\end{equation}
The budget also gives $0\le t\le q/2$.
As a function of $t$, the left side of
\eqref{struct:core-t-quadratic} is concave.  On $[5,q/2]$ its values
at the two endpoints are $23$ and $q^2/4-2$, both positive.
This interval is therefore excluded, and $t\le4$.
\end{proof}

\subsection{Signed moments and two useful deletions}

The weights below express the number of full-degree neighbours of
each vertex through \eqref{struct:core-weight-service}. For two
deleted vertices, the sum of their weights controls the number of
full-degree vertices that remain. The weights may be negative, so we distinguish
their signed moments from those of their positive parts.

Define
\begin{equation}
 w_v=
 \begin{cases}
 r_v+\delta_v-1,&v\in L,\\
 r_v-2,&v\in H,
 \end{cases}
 \qquad
 R_Z=\sum_{z\in Z}r_z.
 \label{struct:core-deletion-weights}
\end{equation}
For every vertex,
\begin{equation}
 d_H(v)=q-w_v-\mathbf1_H(v).
 \label{struct:core-weight-service}
\end{equation}

\begin{lemma}[The signed moment identities]
\label{struct:core-signed-moments}
Under \eqref{struct:core-three-degrees},
\begin{align}
 \sum_vw_v&=2q-t(q+2),
 \label{struct:core-first-moment}\\
 \sum_vw_v^2
 &=q^2+(1-t)q+t^2-3t-2\eta-2R_Z-2u_{HH}.
 \label{struct:core-second-moment}
\end{align}
Writing $w_v^+=\max\{w_v,0\}$, one has
\begin{equation}
 \sum_vw_v^+\le2q,
 \qquad
 \sum_v(w_v^+)^2\ge q^2-27q-4.
 \label{struct:core-positive-moments}
\end{equation}
\end{lemma}

\begin{proof}
Put $\ell=|L|=2q-t$, $h=|H|=q^2-q+t$, and $e_L=e(F[L])$.
Since the vertices of $L\setminus Z$ have degree $q$ and those of
$Z$ have degree $q-1$,
\[
 \sum_vr_v=\sum_{v\in L}d_F(v)=q\ell-t.
\]
Adding $\sum_L(\delta_v-1)=t$ and subtracting $2h$ proves
\eqref{struct:core-first-moment}.

We derive the second identity without an assumption about the signs
of the weights.  Summing \eqref{struct:core-local-count} over $L$ and
then over $H$ gives
\[
 2u_{LL}+u_{LH}=2q^2-\ell+\omega,
 \qquad
 2u_{HH}+u_{LH}=h+\eta.
\]
Subtracting yields
\begin{equation}
 2u_{LL}=q^2-q+\omega-\eta+2u_{HH}.
 \label{struct:core-low-hole-identity}
\end{equation}
The number of covered pairs in $L$ is
$\sum_v\binom{r_v}{2}$, because each such pair has at most one
common neighbour.  Therefore
\begin{equation}
 \sum_vr_v^2=q\ell-t+\ell(\ell-1)-2u_{LL}.
 \label{struct:core-r-square}
\end{equation}
Also
\[
 \omega=2e_L+R_Z,\qquad
 \sum_{v\in H}r_v=q\ell-t-2e_L.
\]
Relative to $\sum_vr_v^2$, replacing $r_v$ by $r_v-2$ on $H$
adds $-4\sum_Hr_v+4h$, and replacing $r_z$ by $r_z+1$ on $Z$
adds $2R_Z+t$.  Thus
\begin{align*}
 \sum_vw_v^2
 &=q\ell-t+\ell(\ell-1)-2u_{LL}
      -4(q\ell-t-2e_L)+4h+2R_Z+t\\
 &=\ell(\ell-1)-3q\ell+4t+4h+4\omega-2R_Z-2u_{LL}\\
 &=\ell(\ell-1)-3q\ell+4t+4h-q^2+q
       +3\omega+\eta-2R_Z-2u_{HH}.
\end{align*}
Now substitute $\ell=2q-t$, $h=q^2-q+t$, and
$\omega=2q-4t-\eta$.  This gives
\eqref{struct:core-second-moment} exactly.

Every low weight is nonnegative.  At a full vertex $r_v\ge1$,
because $a_v\ge2$ and the only positive deficits are one and two.
Thus a negative weight is exactly $-1$, and it occurs precisely at
a full vertex whose only low neighbour belongs to $Z$.
Let $a_-$ be the number of such vertices.  Then
\begin{equation}
 a_-\le e(Z,H)=t(q-1)-R_Z\le t(q-1).
 \label{struct:core-negative-weight-count}
\end{equation}
Consequently
\[
 \sum_vw_v^+
 =2q-t(q+2)+a_-\le2q-3t\le2q,
 \qquad
 \sum_v(w_v^+)^2=\sum_vw_v^2-a_-.
\]
By Lemma~\ref{struct:core-exceptional-capacity},
$t\le4$ and $u_{HH}\le2\eta+1$.
We may use the coarse bounds
\[
 (1-t)q\ge-3q,\quad t^2-3t\ge-2,\quad
 \eta\le2q,\quad R_Z\le4q,\quad u_{HH}\le4q+1,
 \quad a_-\le4q.
\]
Their substitution into \eqref{struct:core-second-moment} proves
the second inequality in \eqref{struct:core-positive-moments}.
\end{proof}

\begin{lemma}[A two-largest-weights estimate]
\label{struct:two-largest-moment}
Let $x_1\ge x_2\ge\cdots\ge0$ be a finite sequence with
$\sum_i x_i\le2q$, and put $W=x_1+x_2$ (adjoining zero terms if
necessary).  If $W\le q$, then
\begin{equation}
 \sum_i x_i^2\le qW.
 \label{struct:two-largest-square-bound}
\end{equation}
\end{lemma}

\begin{proof}
Put $a=x_1$ and $b=x_2=W-a$.  Every remaining term is at most $b$,
so
\[
 \sum_i x_i^2\le a^2+b(2q-a).
\]
Subtracting $qW$ from the last expression gives
$(2a-W)(a-q)\le0$, since $W/2\le a\le W\le q$.
\end{proof}

\begin{proposition}[Two deletions leave many full vertices]
\label{struct:core-two-deletions}
Under \eqref{struct:core-three-degrees}, there are two distinct
vertices $u,v$ with $w_u,w_v\ge0$ and
\begin{equation}
 w_u+w_v\ge q-27.
 \label{struct:core-heavy-pair}
\end{equation}
For $F_0=F-\{u,v\}$, at least
\begin{equation}
 q^2-2q-27
 =N-3(q+1)+\binom32-28
 \label{struct:core-clean-full-count}
\end{equation}
vertices have degree $q+1$ and are adjacent to neither deleted vertex.
\end{proposition}

\begin{proof}
Apply Lemma~\ref{struct:two-largest-moment} to the positive weights.
If their largest-two sum is at most $q$, then
\eqref{struct:core-positive-moments} gives
$W\ge q-27-4/q$.  The weights are integers and $q>4$, so
$W\ge q-27$.  If $W>q$, this conclusion is immediate.
We can realize the two chosen positive-part weights by distinct
vertices of nonnegative actual weight: if at most one weight is
positive, use any other low vertex as the second vertex.  There
are at least $2q-4$ low vertices, and their weights are nonnegative.

Every full vertex outside
$\{u,v\}\cup N_F(u)\cup N_F(v)$ retains its degree in $F_0$.
By \eqref{struct:core-weight-service}, their number is at least
\begin{align*}
 |H|-|\{u,v\}\cap H|-d_H(u)-d_H(v)
 &=|H|-2q+w_u+w_v\\
 &\ge q^2-2q+t-27\ge q^2-2q-27.
\end{align*}
This proves \eqref{struct:core-clean-full-count}.
\end{proof}

\subsection{From the incidence completion to a polarity host}

The incidence-completion and polarity-extension theorems apply with
three omitted points and the clean full-degree set constructed above.

\begin{lemma}[A host after the two deletions]
\label{struct:core-three-puncture-host}
Let $q\ge10^{15}$ be even, let $F$ satisfy
\eqref{struct:core-three-degrees}, and choose $u,v,F_0$ as in
Proposition~\ref{struct:core-two-deletions}.
There are a projective plane $\Pi$ of order $q$, a polarity $\pi$
of $\Pi$, and a three-point set $Q$ such that
\[
 F_0\subseteq P_\pi-Q
\]
as a spanning subgraph, where $P_\pi$ denotes the loopless polarity
graph.  A set $C$ of $q^2-2q-27$ full vertices can be chosen among
the vertices adjacent to neither $u$ nor $v$ so that every old polar
line has at most $31$ points outside $C$.
\end{lemma}

\begin{proof}
Choose $C$ as in \eqref{struct:core-clean-full-count}, of exactly the
displayed size.  On the point set $C$ take the indexed lines
\[
 S_x=N_{F_0}(x)\cap C\qquad(x\in V(F_0)).
\]
Every point lies on exactly $q+1$ indexed lines, and any two lines
meet in at most one point.  The parameters of the fixed-parameter
incidence-completion theorem are
\begin{equation}
 s=3,\qquad t_{\mathrm{inc}}=28,\qquad K=s+t_{\mathrm{inc}}=31.
 \label{struct:core-completion-parameters}
\end{equation}
The shortest-line packing lemma gives $|S_x|\ge q-30$ for every $x$.
In particular the degree deficits $q+1-d_{F_0}(x)$ are at most $31$.
A full vertex $x\in C$ has at most $31$ neighbours outside $C$,
and all its neighbours in $C$ have deficit zero.  Its weighted
neighbour deficit is therefore at most $31^2$.
At the order $N-3$, the exact local identity for this full vertex
is $u_x=a_x-3$.  Hence the uncovered-pair graph on $C$ has maximum
degree at most $31^2$.
Theorem~\ref{inc:fixed-parameter-completion}, with $D=961$,
embeds the entire indexed incidence system into a projective plane
$\Pi$ of order $q$.  Write $p_x$ for the point images of $x\in C$
and $\ell_y$ for the distinct line images of all $y\in V(F_0)$.
The incidences are exact:
\begin{equation}
 p_x\in\ell_y\quad\Longleftrightarrow\quad xy\in E(F_0)
 \qquad(x\in C,\ y\in V(F_0)).
 \label{struct:core-exact-incidences}
\end{equation}

There are three missing lines.  Every point of $C$ is already
incident with its full pencil of $q+1$ indexed lines and therefore
lies on none of them.  Their union has at least $3(q+1)-3=3q$
points.  The complement of $C$ has $3q+28$ points, so at most $28$
of these avoid all three missing lines.  Every indexed line meets
the missing-line union in at most three points; it therefore has
at most $31$ points outside $C$.

Apply Lemma~\ref{geo:bounded-polarity-extension} with $s=3$ and
$t=28$.  The chosen set $C$ has the required size, all its vertices
have degree $q+1$ in $F_0$, and
$q\ge10^{15}>(3+28+2)^2$.
The lemma extends \eqref{struct:core-exact-incidences} to distinct
point images $p_x$ for all $x\in V(F_0)$ and a polarity $\pi$ with
$\pi(p_x)=\ell_x$.
In particular, the old incidences are symmetric:
\begin{equation}
 p_x\in\ell_y\quad\Longleftrightarrow\quad p_y\in\ell_x.
 \label{struct:core-old-symmetry}
\end{equation}
For this old assignment, the pairing of the three omitted points
and lines is uniquely determined by
Lemma~\ref{geo:gram-polarity-extension}.
Let $Q$ be the three unassigned points.
The respected-edge conclusion of
Lemma~\ref{geo:bounded-polarity-extension} gives
$F_0\subseteq P_\pi-Q$.

We verify the stated numerical range of the completion theorem.
For \eqref{struct:core-completion-parameters} its constants are
\[
 K=31,\quad A_0=64,\quad B_0=1856,\quad Y_0=3712,
 \quad\mu=961,\quad C_1=32515,\quad a_0=4525.
\]
Its packing constant is $644$ and its bad-pair threshold is
$105989597184$.  The other polynomial thresholds are at most
$13775263$, except for the Beutelspacher--Metsch condition
$4q>f(a_0)$, where
\[
 f(a)=6a^4+9a^3+19a^2+8a,
 \qquad f(4525)=2516341573744950<4\cdot10^{15}.
\]
Thus all completion conditions hold for $q\ge10^{15}$.
This range also covers all pencil, injectivity, and Gram-extension
inequalities used above.
\end{proof}

\subsection{Reinserting the two deleted vertices}

\begin{theorem}[Recognition of all extremal cores]
\label{struct:all-extremal-core-recognition}
Let $q\ge10^{15}$ be even.  If $F$ is a $C_4$-free graph with
\[
 |V(F)|=q^2+q,\qquad
 e(F)=\frac12q(q+1)^2-q,
\]
then $F$ is obtained by deleting an absolute point from an
orthogonal polarity graph of a projective plane of order $q$.
In particular all its degrees belong to $\{q,q+1\}$, its surplus
$\eta(F)$ is zero, and its completion by the missing absolute point
is unique.
\end{theorem}

\begin{proof}
Theorem~\ref{struct:automatic-fixed-deficit-cap}, with $b=0$, gives
$\Delta(F)\le q+1$ for $q\ge10^9$.
The minimum-degree theorem for capped extremal cores gives
$\delta(F)\ge q-1$.  Thus \eqref{struct:core-three-degrees} holds.
Choose $u,v$ by Proposition~\ref{struct:core-two-deletions}, and apply
Lemma~\ref{struct:core-three-puncture-host} to $F_0=F-\{u,v\}$.
Identify its vertices with their old points in the plane, and put
\[
 B_u=N_F(u)\setminus\{u,v\},\qquad
 B_v=N_F(v)\setminus\{u,v\}.
\]
Each set has size at least $q-2$, and both avoid $C$ by the choice
of the clean full vertices.

For $s\in\{u,v\}$, the distinct polar lines
$\{\pi(x):x\in B_s\}$ intersect pairwise outside $C$; otherwise
two neighbours of $s$ would have another common neighbour in $C$.
They are concurrent at a point $p_s$ outside $C$, by
Lemma~\ref{struct:bounded-pencil} and the bound of $31$ outside
points on each old polar line.
The centre $p_s$ cannot be an old point.  If it were the old point
$x\notin C$, its at least $q-30$ neighbours in $C$ would index
that many lines through $p_s$.  These line indices lie in $C$,
whereas $B_s$ avoids $C$.  Together the two families would have
at least $(q-30)+(q-2)>q+1$ distinct lines through $p_s$.
Thus $p_u,p_v\in Q$.
Moreover $|B_u\cap B_v|\le1$ by $C_4$-freeness.  Equality of the
two centres would put at least $2(q-2)-1>q+1$ distinct lines
through one point.  Therefore $p_u\ne p_v$.
The assignments $u\mapsto p_u$, $v\mapsto p_v$ are injective and
respect all old--new edges.

It remains to check the possible edge between the two new points.
Write $\varepsilon=A_{uv}$ and retain the original deficits
$\delta_u,\delta_v\in\{0,1,2\}$.
The exact edge count after deleting the two vertices is
\begin{equation}
 e(F_0)=M-3q-2+\delta_u+\delta_v+\varepsilon.
 \label{struct:core-old-edge-count}
\end{equation}
Lemma~\ref{struct:even-polarity-bound} gives
\[
 e(P_\pi-Q)\le M-3q+3,
\]
because the three deleted points have degrees at least $q$ and
span at most three edges.
Consequently the number $D_0$ of old host edges absent from $F_0$
satisfies
\begin{equation}
 D_0\le5-\delta_u-\delta_v-\varepsilon\le5.
 \label{struct:core-old-missing-budget}
\end{equation}

Suppose $\varepsilon=1$ but $p_u,p_v$ are nonadjacent in the
polarity graph.  Put $\ell=\pi(p_u)$ and $k=\pi(p_v)$.
Then $p_v\notin\ell$ and $p_u\notin k$.
The rule
\[
 x\in\ell\longmapsto \pi(x)\cap k
\]
is a bijection between the $q+1$ points of $\ell$ and $k$.
Indeed, it is well defined because $x\ne p_v$; two points with
the same image $y$ would force $\pi(y)=\ell$, hence
$y=p_u\notin k$, a contradiction.
Since $B_u\subseteq\ell$ and $B_v\subseteq k$, at least
$|B_u|+|B_v|-(q+1)$ matching pairs lie in $B_u\times B_v$.
At most one pair is a loop, because a loop lies in $\ell\cap k$.
No nonloop edge is counted in both orientations, since that
would require two different vertices in $B_u\cap B_v$.
There are therefore at least
\[
 |B_u|+|B_v|-q-2\ge q-6
\]
distinct nonloop old host edges between these two neighbour sets.
All must be absent from $F_0$, since any present one makes a
four-cycle with $uv$.  This contradicts
$D_0\le5<q-6$.
Thus the edge $uv$, if present, is also respected.

Let $p$ be the remaining point of $Q$.
We have embedded all of $F$ as a spanning subgraph of $P_\pi-p$.
The edge bound and the minimum degree in
Lemma~\ref{struct:even-polarity-bound} give
\[
 M-q=e(F)\le e(P_\pi-p)\le M-q.
\]
All inequalities are equalities.  Hence
$F=P_\pi-p$, $e(P_\pi)=M$, and $d_{P_\pi}(p)=q$.
The polarity has exactly $q+1$ absolute points, and $p$ is one
of them.  Such a polarity is orthogonal; its absolute points
form a line by Lemma~\ref{struct:even-polarity-bound}.

For the surplus assertion, let $\mathcal A$ be this absolute
line and let $c=\pi(\mathcal A)$ be its nucleus.
Then $c\notin\mathcal A$ and $N_{P_\pi}(c)=\mathcal A$.
In $F=P_\pi-p$, the low-degree set is the disjoint union
\[
 X=\mathcal A\setminus\{p\},\qquad Y=N_{P_\pi}(p),
 \qquad |X|=|Y|=q.
\]
Every vertex of this set has degree $q$, and all others have
degree $q+1$.  A full vertex differs from $c$, because $c\in Y$.
Its polar line meets $\mathcal A$ in exactly one point, which
belongs to $X$; it also has exactly one common neighbour with
the nonadjacent absolute point $p$, and this lies in $Y$.
It therefore has exactly two low neighbours.  This proves
$\eta(F)=0$.
The zero-surplus completion theorem
(Theorem~\ref{thm:zero-surplus-completion}) now gives uniqueness
of the missing absolute-point completion.
\end{proof}

% Source: sections/zero_surplus.tex
\section{Zero full-degree surplus}
\label{sec:zero-depth}

Put $n=q^2+q$, $M=q(q+1)^2/2$, and $m_0=M-q$.
For a $C_4$-free graph $F$ on $n$ vertices with
$e(F)=m_0-b$ and $\Delta(F)\le q+1$, write
\[
 \delta_v=q+1-d(v),\qquad
 H=\{v:\delta_v=0\},\qquad L=V(F)\setminus H,
 \qquad a_v=\sum_{w\in N(v)}\delta_w.
\]
We consider the nonnegative full-degree surplus
\[
 \eta=\sum_{v\in H}(a_v-2).
\]
Here $q$ is even and $b$ is a nonnegative integer.  Nonnegativity
follows from the odd order of every full-degree neighbourhood.

\begin{theorem}[Classification at zero surplus]
\label{thm:zero-depth-classification}
Let $b\ge0$ and let $q\ge8192(b+1)^4$ be even.  Suppose that
$F$ is $C_4$-free and
\[
 |V(F)|=q^2+q,\qquad e(F)=m_0-b,\qquad
 \Delta(F)\le q+1,\qquad \eta(F)=0.
\]
Then precisely one of the following holds.
\begin{enumerate}
\item $b=0$, and $F$ is obtained by deleting an absolute point
from a polarity graph of a projective plane of order $q$.
\item $b=1$, and $F$ is obtained by deleting the point whose
polar line consists of the $q+1$ absolute points of a polarity
of a projective plane of order $q$.
\end{enumerate}
In either case the one-point polarity completion is unique on
the labelled vertex set.  In particular, zero surplus is impossible
for $b\ge2$ in the stated range.
\end{theorem}

The $b=0$ conclusion holds already for even $q\ge4$ by the
zero-surplus completion theorem,
Theorem~\ref{thm:zero-surplus-completion}.
The proof below gives a uniform exclusion of every mixed degree
pattern when $b\ge1$.

\subsection{Partners and the low-degree identities}

Let $U$ denote the graph of uncovered pairs, and let $u_v=d_U(v)$.
Two-path counting and the degree sum give
\begin{equation}
 u_v=q\delta_v-1+a_v,\qquad
 \sum_{v\in L}\delta_v=2q+2b.
 \label{eq:depth-local}
\end{equation}
If $\eta=0$, every vertex $v\in H$ has $a_v=2$, so $u_v=1$.
Its unique uncovered partner $f(v)$ is adjacent to $v$.
The codegree commutator gives, for $u,v\in H$,
\begin{equation}
 A_{u,f(v)}=A_{f(u),v}.
 \label{eq:depth-partner-commutator}
\end{equation}
These identities follow directly by commuting
$A^2=qI+J-\operatorname{diag}(\delta)-U$ with $A$.

There is no uncovered pair within $H$ when $q\ge4$.
Indeed, if $f(u)=v\in H$, symmetry gives $f(v)=u$.
Equation~\eqref{eq:depth-partner-commutator} and $C_4$-freeness
show that $v$ is the only full-degree neighbour of $u$.
Since $a_u=2$, at most two neighbours of $u$ belong to $L$,
contradicting $d(u)=q+1\ge5$.
Thus $f(H)\subseteq L$.  Call these low vertices active.
Each full-degree vertex has its partner as its only active neighbour:
an additional active neighbour, together with a full-degree vertex
having that partner, would give a four-cycle by
\eqref{eq:depth-partner-commutator}.

\begin{lemma}
\label{lem:depth-small-deficits}
If $\eta=0$, $q\ge4$ is even, and $q>2b$, then every positive deficit is
one or two, and every deficit-two vertex is active.
\end{lemma}

\begin{proof}
A vertex $w$ with $\delta_w\ge3$ has no full-degree neighbour,
because such a neighbour would have $a_v>2$.
It also has no full-degree uncovered partner, since every such
partner would have to be adjacent to it.
Thus all its uncovered partners lie in $L$, and
\[
 3q-1\le u_w\le |L|-1\le2q+2b-1,
\]
contrary to $q>2b$.

If a deficit-two point $w$ is inactive, it has no full-degree
neighbour: any full-degree neighbour has $w$ as its only low
neighbour, so its uncovered partner must be $w$.
Consequently $a_w\ge q-1$ and $u_w\ge3q-2$.
As before $u_w\le2q+2b-1$, giving $q\le2b+1$.
Evenness and $q>2b$ exclude this possibility.
\end{proof}

Write $X_1$ for the active deficit-one vertices, $X_2$ for the
deficit-two vertices, and $Y$ for the inactive vertices.
Put
\[
 x=|X_1|,\qquad y=|Y|,\qquad t=|X_2|,
 \qquad J=F[L],\qquad j_v=d_J(v),\qquad
 \lambda_v=j_v+\delta_v-1.
\]
All vertices of $Y$ have deficit one.  Every full-degree vertex
has either a pair of low neighbours in $X_1\times Y$, or a
single low neighbour in $X_2$.
No pair in $X_1\times Y$ occurs twice.  Write $Z_w=f^{-1}(w)$
for an active fibre.  Then
\begin{align}
 x+y&=2q+2b-2t,& |H|&=q^2-q-2b+t,\\
 |Z_w|&=q-1-j_w &&(w\in X_2).
 \label{eq:depth-sizes}
\end{align}

\begin{lemma}[Low-degree identities]
\label{lem:depth-low-identities}
Put $s=2b-t$.  Then
\begin{align}
 \sum_{v\in N_J(a)}\lambda_v&=q+s &&(a\in X_1),
 \label{eq:depth-active-unit}\\
 \sum_{v\in N_J(y)}(\lambda_v-1)&=s &&(y\in Y),
 \label{eq:depth-inactive-unit}\\
 \sum_{v\in N_J(w)}(\lambda_v+1)&=q+s-1 &&(w\in X_2).
 \label{eq:depth-active-double}
\end{align}
Moreover, writing $X=X_1\cup X_2$,
\begin{equation}
 d_X(w)=x+t-q-1\qquad(w\in X_2).
 \label{eq:depth-double-fibre-degree}
\end{equation}
\end{lemma}

\begin{proof}
For an active deficit-one point $a$, its full-degree uncovered
partners are precisely its $q-j_a$ fibre members.
Equation~\eqref{eq:depth-local} therefore gives
$a_a+j_a-1$ uncovered partners in $L$.
The covered partners in $L$ are counted by
\[
 (q-j_a)+\sum_{v\in N_J(a)}(j_v-1).
\]
There is no repetition, by $C_4$-freeness.
Since $|L|=2q+2b-t$, subtraction and rearrangement give
\eqref{eq:depth-active-unit}.

An inactive point $y$ has no full-degree uncovered partner.
Its full-degree neighbours each contribute one distinct covered
point of $X_1$, so the same covered-pair count gives
\eqref{eq:depth-inactive-unit}.
For $w\in X_2$, the full-degree uncovered partners number
$q-1-j_w$, and its full-degree neighbours contribute no
covered low point.  Applying the count once more gives
\eqref{eq:depth-active-double}.

To prove \eqref{eq:depth-double-fibre-degree}, choose $z\in Z_w$.
It has $w$ as its sole low neighbour, and exactly $q$
full-degree neighbours.  For every $a\in X\setminus\{w\}$,
the pair $z,a$ is covered exactly once.
If $wa\in E(J)$, its common neighbour is $w$, so $z$ has no
neighbour in $Z_a$.
If $wa\notin E(J)$, its common neighbour is a full-degree vertex
in $Z_a$, giving exactly one neighbour there.
There is no neighbour in $Z_w$, since $z,w$ are uncovered.
Counting the full-degree neighbours of $z$ gives
$q=x+t-1-d_X(w)$, as required.
\end{proof}

\subsection{The pure deficit-two case}
\label{subsec:depth-pure}

If $Y$ is empty, then $X_1$ is empty as well: a full-degree
vertex with a deficit-one partner requires a second low neighbour
in $Y$.
Thus $L=X_2$, $t=q+b$, and
\eqref{eq:depth-double-fibre-degree} gives $j_w=b-1$ for all $w$.
Every fibre has size $q-b$.  Consequently
\[
 q^2-b=|H|=(q+b)(q-b)=q^2-b^2.
\]
It follows that $b=0$ or $b=1$; the former would give $j_w=-1$,
so $b=1$.
The low set has $q+1$ vertices and is independent; all its
vertices have degree $q-1$, and all other vertices have degree
$q+1$.

Adjoin a point $p$ adjacent to the whole low set.
Distinct low vertices have no common neighbour in $F$, so the
extension is $C_4$-free and has $M$ edges.
Its degree-$q$ set is exactly $L$.
Every edge incident with $L$ has codegree zero, by the partner
property and the independence of $L$.
There are exactly $q(q+1)$ uncovered pairs, by the degree count,
and exactly this many edges incident with $L$.
Thus, if $\widehat A$ is the adjacency matrix of the extension,
\[
 B=\widehat A+\operatorname{diag}(\mathbf1_L)
 \quad\text{satisfies}\quad B^2=qI+J.
\]
The rows of $B$ define a projective plane, and symmetry defines
a polarity with absolute set $L$.  The polar line of $p$ is $L$.
Any one-point polarity completion must raise every degree-$q-1$
vertex to degree at least $q$; it must therefore join the new
point to all of $L$.  This proves uniqueness.

\subsection{Excluding mixed deficits at positive edge deficit}

Assume henceforth that $b\ge1$ and $Y\ne\varnothing$.
Every summand in \eqref{eq:depth-inactive-unit} is nonnegative,
because it is evaluated at a neighbour.  Thus
\begin{equation}
 t\le2b,\qquad s=2b-t\ge0.
 \label{eq:depth-t-small}
\end{equation}

No vertex of $X_1$ has $J$-degree one.
Indeed, \eqref{eq:depth-active-unit} would force its unique
neighbour to have $\lambda=q+s$. An active unit-deficit point
has $j\le q-1$, and an active deficit-two point has $j\le q-2$,
because their fibres are nonempty. Thus every low point has
$\lambda\le q$, with equality possible only at an inactive
unit-deficit point of degree $q$ in $J$. It follows that $s=0$,
$t=2b$, and the neighbour is such an inactive point.
Equation~\eqref{eq:depth-inactive-unit} then says that all its
$q$ neighbours have deficit one and $J$-degree one.
None can be inactive, since the inactive identity at such a
leaf would read $q-1=0$.
The $q$ active leaves have fibres of size $q-1$, accounting for
all $|H|=q^2-q$ full-degree vertices.
This leaves no fibre for the $t=2b>0$ deficit-two points,
a contradiction.
Equation~\eqref{eq:depth-active-unit} also excludes degree zero.
Consequently
\begin{equation}
 j_a\ge2\qquad(a\in X_1).
 \label{eq:depth-active-min}
\end{equation}

Let $E$ be the number of full-degree vertices with two low
neighbours, and put $J_2=\sum_{w\in X_2}j_w$.
The fibre count gives
\begin{equation}
 E=q^2-(t+1)q+2t-2b+J_2.
 \label{eq:depth-support-edges}
\end{equation}
Since $E\le x(q-2)$ and $q>2b$, we get $x\ge q-t+1$.
Indeed, replacing $x$ by $q-t$ would make the upper bound
smaller than the right side of \eqref{eq:depth-support-edges}
by at least $q-2b>0$.
Also $E\le yq$ gives $y\ge q-t-1$, and hence
$x\le q+2b-t+1$.
Writing $k=x+t-q$, we have
\begin{equation}
 1\le k\le2b+1,\qquad x\ge q-2b+1.
 \label{eq:depth-k-range}
\end{equation}

For a deficit-two point $w$, equation
\eqref{eq:depth-double-fibre-degree} gives $d_X(w)=k-1$.
If it has a neighbour in $Y$, the inactive identity at that
neighbour gives $j_w\le s$; otherwise $j_w=k-1$.
Thus
\begin{equation}
 j_w\le2b,\qquad\lambda_w\le2b+1\qquad(w\in X_2).
 \label{eq:depth-double-bounded}
\end{equation}

Every inactive point $y$ satisfies $j_y\le s+1$.
For if $j_y>s+1$, it cannot have a neighbour with $\lambda=1$.
Such a neighbour would have to be a unit-deficit leaf.
Active leaves have been excluded; an inactive leaf would force
$j_y-1=s$ by \eqref{eq:depth-inactive-unit}.
All $j_y$ summands in that identity would consequently be at
least one, giving $j_y\le s$, a contradiction.
In particular $\lambda_y=j_y\le2b+1$.

If an active unit-deficit point $a$ has $j_a>s+1$, it has no
neighbour in $Y$, since its contribution $j_a-1$ would exceed
the inactive budget $s$.
Every neighbour of $a$ then has $\lambda\ge2$, by
\eqref{eq:depth-active-min} and the fact that any adjacent
deficit-two point has positive $J$-degree.
Equation~\eqref{eq:depth-active-unit} yields
$2j_a\le q+s$.
Combining all cases, and using $q\ge2b+2$, gives
\begin{equation}
 \max_{v\in L}\lambda_v\le q/2+b.
 \label{eq:depth-max-weight}
\end{equation}

The weighted edge budget at edge deficit $b$ is
\[
 \eta+\sum_{v\in L}(\delta_v-1)(\delta_v+2)
       +\sum_{v\in L}\delta_vj_v=2q+2(q+2)b.
\]
Here $\eta=0$ and the middle sum is $4t$.
Therefore
\begin{equation}
 \sum_{v\in L}\lambda_v
 =2(b+1)q+4b-3t-J_2
 \le2(b+1)q+4b\le3(b+1)q.
 \label{eq:depth-weight-mass}
\end{equation}

Put $D=4(b+1)$.
By the sharper bound in \eqref{eq:depth-weight-mass}, fewer than
$q/2+1$ active unit points have $j_a>D$.
Equations~\eqref{eq:depth-k-range} and $q\ge8b$ show that at
least $q/4$ points of $X_1$ have $j_a\le D$.
Let
\[
 S=\{v\in L:\lambda_v\ge q/(4D)\}.
\]
Equation~\eqref{eq:depth-weight-mass} gives
$|S|\le12D(b+1)=48(b+1)^2$.
Every one of the preceding $q/4$ active points has at least
two neighbours in $S$.
Otherwise \eqref{eq:depth-max-weight} would give
\[
 \sum_{v\in N_J(a)}\lambda_v
 <q/2+b+(D-1)\frac{q}{4D}<3q/4+b<q,
\]
contradicting \eqref{eq:depth-active-unit}.
Two vertices cannot have the same pair of neighbours in $S$,
since $J$ is $C_4$-free.  Hence
\[
 \frac q4\le\binom{|S|}{2}<1152(b+1)^4,
\]
contrary to $q\ge8192(b+1)^4$.
This excludes the mixed case for every $b\ge1$ and completes
the proof of Theorem~\ref{thm:zero-depth-classification}.

\subsection{One edge below the bound}

\begin{theorem}[Nucleus completion one edge below the bound]
\label{thm:nucleus-completion}
Let $q\ge12$ be even.  Suppose that $F$ is a $C_4$-free graph
on $q^2+q$ vertices with $m_0-1$ edges, maximum degree at most
$q+1$, and $\eta=0$.  Then $F$ has exactly $q+1$ vertices
of degree $q-1$, all other vertices have degree $q+1$, and
the vertices of degree $q-1$ are independent.

Adding one new vertex adjacent to these $q+1$ vertices gives
the polarity graph of a projective plane of order $q$.
Its absolute points are exactly the $q+1$ old vertices of
degree $q-1$, and their common neighbour is the new vertex.
This is the unique completion of $F$ to a polarity graph
of order $q$ by adjoining one vertex and preserving the
induced graph on $V(F)$.
\end{theorem}

\begin{proof}
Apply Lemmas~\ref{lem:depth-small-deficits} and
\ref{lem:depth-low-identities} with $b=1$, using the partner and
fibre descriptions in Section~\ref{sec:zero-depth}.
If $Y=\varnothing$, the asserted degree distribution and
independence already follow.  We exclude $Y\ne\varnothing$.
In this case $t\le2$, and
\[
 x+y=2q+2-2t,\qquad |H|=q^2-q-2+t.
\]
Let $E_T$ be the number of edges of the bipartite support
graph on $X_1,Y$.  Put $J_2=\sum_{w\in X_2}j_w$.  Counting
full vertices by their fibres gives
\begin{equation}
 E_T=q^2-(t+1)q+2t-2+J_2.
 \label{eq:nucleus-support-edge-count}
\end{equation}
An active unit vertex has $j_a\le q-1$, while an inactive
unit vertex has $j_y\le q$.  An active deficit-two vertex
has $j_w\le q-2$.  Consequently $\lambda_v\le q$ for
every low vertex.

\paragraph{The case $t=1$.}
Write $X_2=\{w\}$ and $j=j_w$.  Equation
\eqref{eq:depth-active-double} gives $j\ge1$.
An active unit vertex cannot have degree one in $J$,
because \eqref{eq:depth-active-unit} would require its
unique neighbour to have $\lambda=q+1$.  Thus every vertex
of $X_1$ has $j_a\ge2$ and support degree at most $q-2$.
From
\[
 E_T=q(q-2)+j
\]
we obtain $x\ge q+1$ and $y\ge q-1$.  Since $x+y=2q$,
equality holds in both.  Furthermore,
\[
 \sum_{y\in Y}j_y=q|Y|-E_T=q-j.
\]
Equation~\eqref{eq:depth-inactive-unit} has right side
one, so every $y\in Y$ has $j_y\ge1$.  Hence $j\le1$,
and therefore $j=1$ and all $y\in Y$ have $j_y=1$.
The unique neighbour $a$ of $w$ in $J$ satisfies
$\lambda_a=q-1$ by \eqref{eq:depth-active-double}.
Thus $a\in X_1$ and $j_a=q-1$.
It has no neighbour in $Y$, because such a neighbour's
equation \eqref{eq:depth-inactive-unit} would contain
the term $\lambda_a-1=q-2>1$.
All neighbours of $a$ therefore have $\lambda\ge2$.
Equation~\eqref{eq:depth-active-unit} implies
$q+1\ge2(q-1)$, contrary to $q\ge12$.

\paragraph{The case $t=2$.}
Here \eqref{eq:depth-inactive-unit} has right side zero.
Every neighbour of a vertex of $Y$ is consequently a
unit-deficit vertex of degree one in $J$.
We first show that no active unit vertex $a$ has $j_a=1$.
Such a vertex would have a unique neighbour $y$ with
$\lambda_y=q$, necessarily an inactive unit vertex with
$j_y=q$.  All $q$ neighbours of $y$ have deficit one and
degree one in $J$.  None is inactive, since its inactive
equation would contain $\lambda_y-1=q-1>0$.
Thus $x\ge q$ and $y\le q-2$.  But $a$ has support degree
$q-1$, requiring at least $q-1$ inactive unit vertices,
a contradiction.

It follows that all active unit vertices have $j_a\ge2$.
For each $w\in X_2$, equation
\eqref{eq:depth-active-double} has right side $q-1>0$,
so $j_w\ge1$ and $J_2\ge2$.  From
\[
 E_T=(q-1)(q-2)+J_2
\]
and the support-degree bounds, we obtain $x\ge q$ and
$y\ge q-2$.  Since $x+y=2q-2$, we have $x=q$, $y=q-2$.
There are no edges in $J$ between $Y$ and $X$, because
all active unit vertices have $j_a\ge2$ and every active
deficit-two vertex has $\lambda_w\ge2$.
Therefore \eqref{eq:depth-double-fibre-degree} gives
$j_w=d_X(w)=1$ for both deficit-two vertices.
For either one, its unique low neighbour $a$ has
$\lambda_a=q-2$ by \eqref{eq:depth-active-double}.
As $q-2>2$, this neighbour lies in $X_1$ and has $j_a=q-2$.
Every neighbour of $a$ is active and has $\lambda\ge2$.
Equation~\eqref{eq:depth-active-unit} now gives
$q\ge2(q-2)$, again a contradiction.

\paragraph{The case $t=0$.}
All low deficits are one, and
\[
 E_T=(q-2)(q+1),\qquad x+y=2q+2.
\]
Since the active equation has right side $q+2$, every
active vertex has $j_a\ge2$.  The support-degree bounds
give $x\ge q+1$ and $y\ge q-1$.  Thus $x$ is one of
$q+1,q+2,q+3$.  Every inactive vertex has $j_y\ge1$,
because its equation has right side two.

If $x=q+3$ and $y=q-1$, then
\[
 \sum_{y\in Y}j_y=q(q-1)-E_T=2<|Y|,
\]
a contradiction.

If $x=y=q+1$, then
\[
 \sum_{a\in X_1}j_a=q(q+1)-E_T=2(q+1),
\]
so all active vertices have degree two in $J$.
An inactive vertex of degree at least four cannot have
an inactive neighbour: the latter's equation would contain
a term at least three.  All its neighbours would be active
vertices of degree two, in which case its own inactive
equation would make its degree equal to two.  Hence every
inactive vertex has degree at most three.
For an active vertex, the sum of the degrees of its two
low neighbours is then at most six, whereas its active
equation requires that sum to be $q+2>6$.

It remains that $x=q+2$, $y=q$.  In this case
\begin{equation}
 \sum_{y\in Y}j_y=q+2,\qquad
 \sum_{a\in X_1}j_a=3q+2.
 \label{eq:nucleus-two-low-sums}
\end{equation}
Since every inactive vertex has positive degree, its
degree is at most three.  If an active vertex has degree
at least four, it has no inactive neighbour, and all its
neighbours have degree at least two.  Its active equation
therefore bounds its degree by
\[
 d_*=(q+2)/2.
\]
The same bound also holds for every other low vertex.
Let $n_2$ be the number of active vertices of degree two
in $J$.  Equation~\eqref{eq:nucleus-two-low-sums} yields
\begin{equation}
 n_2=4+\sum_{\substack{a\in X_1\\j_a\ge4}}(j_a-3).
 \label{eq:nucleus-degree-two-count}
\end{equation}
For each of these $n_2$ vertices, the two neighbouring
degrees sum to $q+2=2d_*$.  Both neighbours must therefore
have degree exactly $d_*$, and both lie in $X_1$.
There are at most five such heavy vertices, since their
degree sum is at most $3q+2<6d_*$.  No two degree-two
vertices have the same heavy neighbour pair, by
$C_4$-freeness.  Consequently $n_2\le\binom52=10$.
On the other hand, $n_2\ge4$ ensures the existence of at
least two heavy vertices.  Their contributions to
\eqref{eq:nucleus-degree-two-count} give
\[
 n_2\ge4+2(d_*-3)=q\ge12,
\]
the final contradiction.

We have proved $Y=\varnothing$.  The pure deficit-two argument in
Section~\ref{subsec:depth-pure} gives the asserted degree distribution,
completion, and uniqueness.
\end{proof}

% Source: sections/sharp_supersaturation.tex
\section{Sharp supersaturation from polarity structure}
\label{sec:applications}
\label{sharp:section}

Proposition~\ref{prop:polarity-price} gives a lower bound for the
cycles created by each new edge after a point deletion.
Its edge-disjointness assertion allows missing edges of the
containing polarity graph to be accounted for separately.
We first apply this to modifications of an extremal core, and
then to an arbitrary core supplied by Theorem~\ref{stab:main}.

\subsection{Modifications of an extremal core}

The old edges supporting the four-cycles created by one added edge
in a polarity graph are pairwise disjoint.  This permits several
edge deletions before the sharp lower bound is lost.

\begin{theorem}
\label{thm:linear-edit-range}
Let $q\ge10^{15}$ be even.  Suppose $G$ has $q^2+q$ vertices
and $m_0+1$ edges, and $F$ is a $C_4$-free graph on the same
vertex set with $m_0$ edges.  If
\[
 b=|E(F)\setminus E(G)|\le q-2,
\]
then
\[
 \Nfour(G)\ge(b+1)(q-1-b)\ge q-1.
\]
The same conclusion holds for every $q\ge2$, retaining
$0\le b\le q-2$, when $F$ is already known to be an
absolute-point deletion of a polarity graph.
\end{theorem}

\begin{proof}
By Theorem~\ref{struct:all-extremal-core-recognition}, write
$F=\mathcal P-p$, with $p$ absolute.
Put $D=E(F)\setminus E(G)$ and $A=E(G)\setminus E(F)$.
The edge counts give $|D|=b$ and $|A|=b+1$.
For each $e\in A$, Proposition~\ref{prop:polarity-price} supplies
at least $q-1$ four-cycles in $F+e$, whose old edge sets are
pairwise disjoint.  Deletion of $D$ destroys at most $b$ of them.
Every surviving cycle contains exactly one member of $A$.
The cycles counted for different members of $A$ are therefore
distinct, and summation gives the first inequality.
The second follows from
\[
 (b+1)(q-1-b)-(q-1)=b(q-2-b)\ge0.
\]
\end{proof}

\begin{corollary}
\label{cor:counterexample-distance}
For even $q\ge10^{15}$, a graph on $q^2+q$ vertices with
$m_0+1$ edges and fewer than $q-1$ four-cycles must satisfy
\[
 |E(F)\setminus E(G)|\ge q-1
\]
for every $C_4$-free graph $F$ on the same vertex set with
$m_0$ edges.  Its four-cycles have no common edge.
\end{corollary}

\begin{proof}
The distance statement is the contrapositive of
Theorem~\ref{thm:linear-edit-range}.
If one edge met every four-cycle, deleting it would give a graph
$F$ as in that theorem with $b=0$.
\end{proof}


\subsection{Counting the edges outside a polarity host}

\begin{proposition}
\label{sharp:host-count}
Let $q\ge4$ be even, and let $G$ have $N-1$ vertices and
$m_0+1$ edges.  Suppose that $G$ has a spanning $C_4$-free
subgraph $F$ with $m_0-b$ edges, where $0\le b\le q-2$,
and that $F$ is a spanning subgraph of $K=P-p$ for a
polarity graph $P$ of a projective plane of order $q$.
Then
\begin{equation}
 \Nfour(G)\ge q-1.
 \label{sharp:sharp-host-bound}
\end{equation}
\end{proposition}

\begin{proof}
The even-order polarity bound
(Lemma~\ref{struct:even-polarity-bound}) gives
$e(P)\le M$ and $d_P(p)\ge q$.
Thus $e(K)\le m_0$.  Put
\[
 d=m_0-e(K),\qquad
 c=|E(K)\setminus E(G)|,\qquad
 a=|E(G)\setminus E(K)|.
\]
Since $F\subseteq G\cap K$,
\begin{equation}
 0\le d\le b,\qquad 0\le c\le b-d,\qquad a=c+d+1.
 \label{sharp:edge-bookkeeping}
\end{equation}

Fix $e\in E(G)\setminus E(K)$.  If $K+e$ has at least
$L_0$ four-cycles, Proposition~\ref{sharp:puncture-price} shows
that deleting the $c$ absent host edges destroys at most
$c$ of them.  At least $L_0-c$ such cycles remain in $G$.
Each has exactly one edge outside $K$, namely $e$.
The collections obtained for different $e$ are therefore
disjoint.  We may sum these contributions over all $a$
edges outside $K$.

If $d=0$, equality in
$e(K)=e(P)-d_P(p)\le M-q=m_0$ forces $e(P)=M$ and
$d_P(p)=q$.  In particular $p$ is absolute.
Proposition~\ref{sharp:puncture-price} and
\eqref{sharp:edge-bookkeeping} give
\[
 \Nfour(G)\ge(c+1)(q-1-c)
 =q-1+c(q-2-c)\ge q-1,
\]
because $0\le c\le b\le q-2$.

If $d\ge1$, then $c\le q-3$ and $a\ge c+2$.
The arbitrary-puncture bound gives
\[
 \Nfour(G)\ge(c+d+1)(q-2-c)
 \ge(c+2)(q-2-c)
 =q-1+(c+1)(q-3-c)\ge q-1.
\]
All lower bounds being summed are positive in the indicated
ranges.  This proves \eqref{sharp:sharp-host-bound}.
\end{proof}

\subsection{The edge-transversal consequence}



\begin{proof}[Proof of Corollary~\ref{sharp:small-transversal}]
Choose an edge transversal and enlarge it, if necessary,
to an edge set $T$ of size exactly $t$.
There are enough edges for this enlargement under
\eqref{sharp:threshold}.  Its deletion leaves a
$C_4$-free spanning graph
\[
 F=G-T,\qquad e(F)=m_0-(t-1).
\]
Apply the fixed-deficit stability theorem
(Theorem~\ref{stab:main}) with $b=t-1$.
The required threshold is exactly
$q\ge10^{18}(b+1)^{16}=10^{18}t^{16}$.
It supplies a polarity graph $P$ and a point $p$ such
that $F\subseteq P-p$ as a spanning subgraph.
Also $b=t-1\le q-2$ under \eqref{sharp:threshold}.
Proposition~\ref{sharp:host-count} now proves the result.
\end{proof}

\begin{corollary}[A necessary transversal size for a sharp counterexample]
\label{sharp:counterexample-transversal}
Let $q\ge10^{18}$ be even, and let $G$ have $q^2+q$
vertices and $m_0+1$ edges.  If $\Nfour(G)\le q-2$, then
\begin{equation}
 \tau_4(G)>
 \left(\frac{q}{10^{18}}\right)^{1/16},
 \qquad\text{equivalently}\qquad
 \tau_4(G)\ge
 \left\lfloor\left(\frac{q}{10^{18}}\right)^{1/16}\right\rfloor+1.
 \label{sharp:necessary-transversal}
\end{equation}
\end{corollary}

\begin{proof}
Set $t=\lfloor(q/10^{18})^{1/16}\rfloor\ge1$.
Then $q\ge10^{18}t^{16}$.
If $\tau_4(G)\le t$, Corollary~\ref{sharp:small-transversal}
contradicts $\Nfour(G)\le q-2$.
\end{proof}

% Source: sections/further_questions.tex
\section{Further questions}
\label{sec:questions}

\begin{question}
\label{question:sharp}
Does $h(q^2+q)=q-1$ hold for all sufficiently large powers of two $q$?
\end{question}

Theorem~\ref{thm:main} gives the order of magnitude on this sequence.
For even $q\ge10^{18}$, Corollaries~\ref{cor:counterexample-distance}
and~\ref{sharp:counterexample-transversal} impose two simultaneous
conditions on a graph $G$ with $n$ vertices, $m_0+1$ edges and at most
$q-2$ four-cycles:
\[
 \begin{gathered}
 |E(F)\setminus E(G)|\ge q-1
 \quad\text{for every $C_4$-free $F$ on the same vertices with $m_0$ edges},\\
 \tau_4(G)>\left(\frac{q}{10^{18}}\right)^{1/16}.
 \end{gathered}
\]
Thus the sharp question concerns graphs far from every extremal core
whose four-cycles require a growing edge transversal.

If $Q=\Nfour(G)\le q-2$, choosing one edge from each four-cycle
gives a transversal of size at most $q-2$. A minimum transversal
$T$ therefore leaves a $C_4$-free spanning graph
\[
 F=G-T,\qquad e(F)=m_0-b,\qquad
 b=|T|-1\le q-3.
\]
This deficit may be proportional to $q$, whereas
Theorem~\ref{stab:main} applies under
$q\ge10^{18}(b+1)^{16}$.
The cores arising in this way carry additional information:
for every $e\in T$, minimality supplies a four-cycle whose only
edge in $T$ is $e$, hence a three-edge path in $F$ joining the
endpoints of $e$.
Extending the polarity embedding to these cores, or exploiting
the incidence of their associated paths to obtain a smaller
transversal, would address the remaining range.

A second question is the quantitative dependence in the stability
theorem. Its proof supplies explicit polynomial sufficient bounds
for the degree restriction and the geometric embedding.
Determining the largest deficit interval in which every core is
contained in a one-point deletion of a polarity graph would also
clarify the relation between structural stability and the sharp
supersaturation value.

\appendix
% Source: sections/incidence_completion.tex
\section{Incidence completion}
\label{inc:general-incidence-section}

We complete partial incidence structures with a fixed number of missing
indexed lines.  Deleting one indexed line and applying an integer
packing identity supplies the minimum line size required by the
completion argument.


\subsection{The finite-geometric inputs}

We use the following form of Metsch's clique theorem
\cite[Result~2.2]{Metsch1995Grassmann}, also stated explicitly in
\cite[Theorem~2.7]{Kivva2021Spectral}.
Let $\lambda_1,\lambda_2,\mu$ be positive integers.
Suppose a connected graph has between $\lambda_1$ and $\lambda_2$
common neighbours at every adjacent pair, at most $\mu$ common
neighbours at every nonadjacent pair, and maximum degree at most $k$.
If an integer $s\ge1$ satisfies
\begin{equation}
 2\lambda_1-\lambda_2>(2s-1)(\mu-1)-1,
 \qquad
 k<(s+1)(\lambda_1+1)-\frac{s(s+1)}2(\mu-1),
 \label{geo:Metsch-conditions}
\end{equation}
then the maximal cliques of size at least
$\lambda_1+2-(s-1)(\mu-1)$ cover every edge exactly once,
and each vertex lies in at most $s$ of them.
We apply this statement separately to connected components.

The embedding theorem of Beutelspacher and Metsch
\cite{BeutelspacherMetsch1987}, in the form of
\cite[Theorem~2.2.1]{Beutelspacher1990}, says the following.
The order of a finite linear space is its maximum point degree minus one.
A finite linear space with maximum point degree $q+1$ and
minimum line size at least $q+1-a$ embeds in a projective plane
of order $q$ whenever
\[
 4q>f(a):=6a^4+9a^3+19a^2+8a.
\]
Indeed, the semiaffine parameter, defined as the maximum of
$r_P-k_\ell$ over nonincident point--line pairs, is at most $a$.
In the application below every point has degree exactly $q+1$.
The input is applied after every pair of points has been assigned
its unique line.

\subsection{Packing and completion}

The packing argument uses indexed subsets as lines, allowing
empty or singleton lines after restriction. Before applying the
embedding theorem, we construct a finite linear space in which
every pair of points lies on exactly one line and every line has
at least two points.

\begin{lemma}[The general packing identity and the shortest line]
\label{inc:general-packing}
Let $s\ge1$ and $t\ge0$ be integers, put $N=q^2+q+1$, and suppose a
finite partial linear space has
\[
 m=N-s,\qquad
 b=N-s(q+1)+\binom{s}{2}-t
   =q^2-(s-1)q+\beta,
 \qquad \beta=\frac{(s-1)(s-2)}2-t,
\]
indexed lines and points respectively.  Every point is to lie on
exactly $q+1$ indexed lines.  Distinct indexed lines intersect in at
most one point.  Write $r_v$ for their sizes, and $u$ for the number
of uncovered unordered point pairs.  Then
\begin{equation}
 2u+\sum_v(r_v-q+s-1)(r_v-q+s-2)=2tq+C_{s,t},
 \label{inc:general-packing-identity}
\end{equation}
where
\[
 C_{s,t}=\beta^2+(2s-3)\beta-(s-1)^2(s-2).
\]
If $q\ge s^4+2s^3+1$, then every indexed line has size at least
\begin{equation}
 r_v\ge q-s+1-t.
 \label{inc:automatic-minline}
\end{equation}
In particular, for fixed $s,t$ and sufficiently large $q$, the
number of uncovered pairs is at most $(t+1)q$.
\end{lemma}

\begin{proof}
We have $\sum_v r_v=b(q+1)$ and
$\sum_vr_v(r_v-1)=b(b-1)-2u$.  Expanding the left side of
\eqref{inc:general-packing-identity} gives the stated identity.
Every summand is a product of two consecutive integers, hence is
nonnegative.  This proves the last assertion once $q>|C_{s,t}|$.

Fix an indexed line of size $r$, delete this line and all its points,
and restrict every other indexed line to the remaining points.
The new counts are $m'=N-s-1$ and $b'=b-r$.  Each remaining point
still has degree $q+1$.  The pair count and Cauchy's inequality give
\[
 \frac{b'^2(q+1)^2}{m'}
 \le\sum_v(r'_v)^2\le b'(b'+q).
\]
If $b'=0$, the claimed lower bound on $r$ is immediate.  Otherwise
\[
 b'\le\frac{q(q^2+q-s)}{q+s+1}
     =q^2-sq+s^2-\frac{s^2(s+1)}{q+s+1}
     <q^2-sq+s^2.
\]
Suppose $b'>q^2-sq+s(s-1)/2$, and write $b'=q^2-sq+\beta'$.
Then
\[
 \frac{s(s-1)}2+1\le\beta'\le s^2-1.
\]
The same packing expansion, with $s+1$ in place of $s$, is
\[
 2u'+\sum_v(r'_v-q+s)(r'_v-q+s-1)
 =[s(s-1)-2\beta']q
   +\beta'^2+(2s-1)\beta'-s^2(s-1).
\]
Its right side is at most $-2q+s^4+2s^3<0$, while its left side is
nonnegative.  Thus $b'\le q^2-sq+s(s-1)/2$, and subtracting this
from $b$ gives \eqref{inc:automatic-minline}.
\end{proof}

\begin{theorem}[Fixed-parameter incidence completion]
\label{inc:fixed-parameter-completion}
Fix integers $s\ge1$, $t\ge0$, and $D\ge0$.  For all sufficiently
large integers $q$, the following holds.  Let a finite partial linear
space have
\[
 |\mathcal L|=q^2+q+1-s,\qquad
 |P|=q^2+q+1-s(q+1)+\binom{s}{2}-t,
\]
every point on exactly $q+1$ indexed lines, and distinct indexed
lines intersecting in at most one point.  If its uncovered-pair
graph $U$ has $\Delta(U)\le D$, then $U$ is empty, and the whole
incidence structure embeds in a projective plane of order $q$.
The lower bound on $q$ depends only on $s,t,D$.
The inequalities \eqref{inc:completion-packing}--\eqref{inc:BM-bound}
below give sufficient numerical conditions.
\end{theorem}

\begin{proof}
We retain the notation $b,\beta,C_{s,t}$ from
Lemma~\ref{inc:general-packing} and define
\begin{align*}
 K&=s+t,& A_0&=2(K+1),& D_*&=\max\{D,2\},\\
 B_0&=A_0(t+1),&Y_0&=2B_0,&\mu&=K^2,\\
 C_1&=s+Y_0+(K-1)(\mu-1),&&&
 a_0&=s+Y_0+(K-1)\max\{t-1,0\}.
\end{align*}
All these constants are independent of $q$.
It suffices to assume
\begin{align}
 q&\ge s^4+2s^3+1,\qquad q>|C_{s,t}|,
       \label{inc:completion-packing}\\
 q&>A_0\binom{B_0+1}{2}D_*,
       \label{inc:completion-bad-pairs}\\
 q&>2\{2(s+2+Y_0)+K^2+(2K-1)(\mu-1)+1\},
       \label{inc:metsch-bound-one}\\
 q&>2(K+1)(s+1+Y_0)+K(K+1)(\mu-1),
       \label{inc:metsch-bound-two}\\
 q&>\max\{s+Y_0,\ a_0,\ \beta+(t+1)(K-1)\},
       \label{inc:completion-clique-sizes}\\
 q&>2(K+1)(C_1+1),
       \label{inc:completion-exact-cliques}\\
 q&>\max\{2K,\ K+Y_0(Y_0-1)\},
       \label{inc:completion-restoration}\\
 4q&>f(a_0)=6a_0^4+9a_0^3+19a_0^2+8a_0.
       \label{inc:BM-bound}
\end{align}
The first two conditions control packing and the deletion of badly
separated line pairs.  The next four give an exact clique decomposition
at each remaining index.  The last two permit the geometric embedding
and restoration of the deleted indices.

By the packing lemma, $e(U)\le(t+1)q$ and every line has at least
$q+1-K$ points.  Write $S_v\subseteq P$ for an indexed line and
$d_v=q+1-|S_v|$.  A nonempty $S_v$ meets exactly $1+q|S_v|$ indexed
lines, including itself.  Since there are $N-s$ indices,
$|S_v|\le q$ for $q>s$.  Consequently
\begin{equation}
 1\le d_v\le K.
 \label{inc:general-line-deficits}
\end{equation}

\paragraph{Removing the bounded set of badly separated line pairs.}
Let $R$ be the graph on the line indices in which adjacency means
disjointness.  For disjoint point sets $X,Y$, let $h(X,Y)$ count
uncovered pairs with one end in each.  Direct inclusion--exclusion gives
\begin{align}
 d_R(v)&=qd_v-s,\label{inc:R-degree}\\
 |N_R(v)\cap N_R(w)|
 &=q-s-1+(d_v-1)(d_w-1)-h(S_v,S_w)
       &&(vw\in E(R)).\label{inc:R-adj}
\end{align}
For distinct nonadjacent indices $v,w$, write
$S_v\cap S_w=\{p\}$. Then
\begin{equation}
 |N_R(v)\cap N_R(w)|
 =d_vd_w-s-h(S_v\setminus\{p\},S_w\setminus\{p\}).
 \label{inc:R-nonadj}
\end{equation}
Thus nonadjacent codegrees are at most $\mu$.

Call $vw\in E(R)$ bad if $h(S_v,S_w)\ge q/A_0$, and denote its
set of cross-holes by $F_{vw}$.  Two different such sets intersect
in at most $D_*$ pairs.  If the edges share an index, every common
hole is incident with the at most one intersection point of their
other two lines, so the bound is $D$.  With four distinct indices,
the two possible ways to match the line pairs give at most two
common holes.
If there were $B_0+1$ bad edges, inclusion--exclusion would give
\[
 e(U)\ge(t+1)q+q/A_0-\binom{B_0+1}{2}D_*>(t+1)q
\]
by \eqref{inc:completion-bad-pairs}.  Hence there are at most $B_0$
bad edges.  Delete their endpoints, a set $Y$ of size at most $Y_0$,
and let $R_0$ be the induced graph on the remaining indices.
For its vertices,
\begin{equation}
 qd_v-s-Y_0\le d_{R_0}(v)\le qd_v-s.
 \label{inc:R0-degree}
\end{equation}
Its adjacent codegrees lie between
\[
 \lambda_1=\lfloor(1-1/A_0)q\rfloor-(s+1+Y_0),
 \qquad\lambda_2=q+K^2,
\]
and its nonadjacent codegrees are at most $\mu$.

\paragraph{The exact clique count at a line index.}
Apply Metsch's theorem, in the form stated in
\eqref{geo:Metsch-conditions}, with clique-count parameter $K$
and maximum-degree bound $Kq$.
The bound
$\lambda_1\ge(1-1/A_0)q-(s+2+Y_0)$ and
$1-2/A_0\ge1/2$ show that
\eqref{inc:metsch-bound-one} implies its first inequality.
Since $(K+1)(1-1/A_0)-K=1/2$,
\eqref{inc:metsch-bound-two} implies its second inequality.
The theorem applies componentwise; there are no isolated vertices
by \eqref{inc:completion-clique-sizes}.
The maximal cliques selected by the theorem form a family $\mathcal K$
covering each edge once, with at most $K$ cliques at any vertex,
and
\begin{equation}
 |J|\ge(1-1/A_0)q-C_1\qquad(J\in\mathcal K).
 \label{inc:initial-cliques}
\end{equation}
On the other hand, their original line sets are pairwise disjoint,
so $|J|(q+1-K)\le b$.  Since
\[
 (q+t+1)(q+1-K)-b=q-\beta-(t+1)(K-1),
\]
we have
\begin{equation}
 |J|\le q+t
 \label{inc:clique-upper}
\end{equation}
by \eqref{inc:completion-clique-sizes}.

Let $k_v$ count cliques containing $v$.  Edge uniqueness implies
$d_{R_0}(v)=\sum_{J\ni v}(|J|-1)$.
If $k_v\le d_v-1$, then
\[
 d_{R_0}(v)\le(d_v-1)(q+t-1)<qd_v-s-Y_0
\]
by \eqref{inc:completion-clique-sizes}, a contradiction.
If $k_v\ge d_v+1$, then
\[
 d_{R_0}(v)\ge(d_v+1)((1-1/A_0)q-C_1-1)>qd_v-s
\]
by \eqref{inc:completion-exact-cliques}, also a contradiction.
Thus
\begin{equation}
 k_v=d_v.
 \label{inc:exact-clique-count}
\end{equation}
Put $b_v=|N_R(v)\cap Y|\le Y_0$.  The exact degree identity now is
\[
 \sum_{J\ni v}(q+1-|J|)=s+b_v.
\]
Every summand is at least $1-t$, by
\eqref{inc:clique-upper}, and there are at most $K$ summands.
It follows that every clique has size at least $q+1-a_0$.

\paragraph{Embedding a genuine linear space and restoring the indices.}
On the point set $I\setminus Y$, include the original restricted
point pencils
\[
 L_p=\{v\in I\setminus Y:p\in S_v\}\qquad(p\in P)
\]
as lines, and also include the cliques of $\mathcal K$ as lines.
Every pair of indices lies on exactly one line: intersecting
original lines use their unique common point, and disjoint ones
use their unique clique.  All these lines are distinct, any two
intersect in at most one point, and every point $v$ has degree
$|S_v|+d_v=q+1$.  Original pencil lines have size at least
$q+1-Y_0$, and clique lines have size at least $q+1-a_0$.
Since $a_0\ge Y_0$, the resulting genuine linear space embeds in a
projective plane of order $q$ by the Beutelspacher--Metsch theorem
\cite[Theorem 2.2.1]{Beutelspacher1990} and
\eqref{inc:BM-bound}.
The embedded incidences are exact: each assigned point already
has its $q+1$ prescribed lines, exhausting its ambient pencil.

Write $p_v$ for the assigned point of $v\in I\setminus Y$ and
$\ell_p$ for the plane line of $L_p$.  Each $\ell_p$ contains at
most $Y_0$ points outside the assigned set.
For a deleted index $v\in Y$, the at least $q+1-K$ distinct lines
$\ell_p$, $p\in S_v$, intersect pairwise outside that set.
Condition \eqref{inc:completion-restoration} permits
Lemma~\ref{struct:bounded-pencil} to assign their common point to $v$.
Two deleted indices cannot receive the same point: their line
families share at most one member, and together would have at
least $2(q+1-K)-1>q+1$ lines, again by
\eqref{inc:completion-restoration}.
Thus all original indexed lines have distinct point images.
For each $p\in P$, its $q+1$ prescribed indexed-line points now
fill $\ell_p$.  The intersection of two such plane lines is
therefore an assigned indexed-line point, so the original two
points are covered by a line.  Hence $U$ is empty.  Dualizing the
plane embeds the entire original incidence structure.
The numerical conditions involve only $s,t,D$, proving the theorem.
\end{proof}

% Source: sections/polarity_extension.tex
\section{Polarity extension}
\label{geo:polarity-extension-section}

\subsection{A matrix criterion for unique extension}
\label{geo:gram-extension-section}

F\"uredi's partial-symmetry criterion, recalled in
\cite[Lemma~2.1]{HeMaYang2023}, assumes symmetry of every
entry involving a sufficiently large prescribed set of indices.
The following lemma starts with a symmetric principal block
and determines the omitted point--line matching.

\begin{lemma}[Extending symmetric incidence across finitely many omissions]
\label{geo:gram-polarity-extension}
Let $\Pi$ be a projective plane of order $q$, put $N=q^2+q+1$,
and let $s\ge1$ with $q\ge2s$.
Suppose $p_1,\ldots,p_{N-s}$ are distinct points and
$\ell_1,\ldots,\ell_{N-s}$ are distinct lines such that
\[
 p_i\in\ell_j\quad\Longleftrightarrow\quad p_j\in\ell_i
 \qquad(1\le i,j\le N-s).
\]
Then there is a unique polarity $\pi$ of $\Pi$ satisfying
$\pi(p_i)=\ell_i$ for every $i$.
\end{lemma}

\begin{proof}
Let $Q$ be the $s$ omitted points and $\Lambda$ the $s$ omitted
lines.  With the prescribed old point and line orders, write the
full incidence matrix of $\Pi$ as
\[
 M=\begin{pmatrix}B&X\\Y^{\mathsf T}&Z\end{pmatrix}.
\]
Thus $B$ is the old-point--old-line incidence matrix,
$X$ records incidences of old points with $\Lambda$, and $Y$
records incidences of old lines with $Q$.
The hypothesis says $B=B^{\mathsf T}$.
Since every line and point has $q+1$ incidences and every two
distinct points or lines have exactly one common incidence,
\[
 MM^{\mathsf T}=M^{\mathsf T}M=qI+J.
\]
Comparing the upper-left blocks therefore gives
\begin{equation}
 XX^{\mathsf T}=YY^{\mathsf T}.
 \label{geo:equal-incidence-Grams}
\end{equation}

For every $\lambda\in\Lambda$, there is an old point on
$\lambda$ and on no other omitted line.
Indeed, among its $q+1$ points, at most $s$ lie in $Q$ and at
most $s-1$ are intersections with other omitted lines, leaving
at least $q-2s+2>0$ choices.
Consequently $X$ contains every standard unit row of
$\{0,1\}^s$.
For the corresponding $s$ rows of $Y$,
\eqref{geo:equal-incidence-Grams} gives squared norm one
and pairwise inner product zero.
They are therefore the $s$ different standard unit rows, in
some order.
After a unique permutation of the columns of $Y$, these rows
agree with the chosen rows of $X$.
Inner products with these unit rows then force every row to
agree, so $Y=X$ after that permutation.
This fixes the required bijection from $Q$ to $\Lambda$.

Order the omitted points accordingly.  We now have
\[
 M=\begin{pmatrix}B&X\\X^{\mathsf T}&Z\end{pmatrix}.
\]
The upper-right blocks of $MM^{\mathsf T}=M^{\mathsf T}M$
give
\[
 BX+XZ^{\mathsf T}=BX+XZ,
 \qquad X(Z-Z^{\mathsf T})=0.
\]
The unit rows show that $X$ has column rank $s$, and hence
$Z=Z^{\mathsf T}$.
Thus the entire reordered incidence matrix is symmetric.
The resulting point-to-line bijection is a polarity extending
all prescribed assignments.
The omitted bijection was forced by the unit rows, proving
uniqueness.
\end{proof}


\subsection{A bounded incidence defect}

The symmetric incidence assignment extends even when the clean point
set omits a bounded number of points in addition to those on the
missing lines.

\begin{lemma}[Polarity extension with additional omitted points]
\label{geo:bounded-polarity-extension}
Let $\Pi$ be a projective plane of order $q$, and put
$N=q^2+q+1$. Let $s\ge1$ and $t\ge0$ be integers, and suppose
$q>(s+t+2)^2$.
Let $F$ be a $C_4$-free graph on a set $V_0$ of $N-s$ vertices,
and let $C\subseteq V_0$ satisfy
\[
 d_F(u)=q+1\quad(u\in C),\qquad
 |C|\ge N-s(q+1)+\binom{s}{2}-t.
\]
Suppose there are distinct points $p_u$ for $u\in C$ and distinct
lines $\ell_v$ for $v\in V_0$ in $\Pi$, with exact incidences
\[
 p_u\in\ell_v\quad\Longleftrightarrow\quad uv\in E(F)
 \qquad(u\in C,\ v\in V_0).
\]
Then the assignment extends to distinct points $p_v$ for every
$v\in V_0$ and to a polarity $\pi$ of $\Pi$ with
$\pi(p_v)=\ell_v$. In particular, $F$ is a spanning subgraph
of $H-Q$, where $H$ is the loopless polarity graph of $\pi$
and $Q$ is the set of $s$ unassigned plane points.
\end{lemma}

\begin{proof}
Write $a=s+t$, and identify $C$ with its point images.
There are exactly $s$ missing lines, denoted by $\Lambda$.
Every point of $C$ is already incident with $q+1$ old lines,
so it lies on no missing line. The union of $s$ lines has at
least $s(q+1)-\binom{s}{2}$ points. Hence at most $t$ points
outside $C$ avoid all missing lines. Every old line therefore
contains at most $s+t=a$ points outside $C$. Consequently
\begin{equation}
 |N_F(v)\cap C|=|\ell_v\cap C|\ge q+1-a
 \qquad(v\in V_0).
 \label{geo:old-line-density}
\end{equation}

For $v\in V_0\setminus C$, consider the lines $\ell_u$ indexed
by $u\in N_F(v)\cap C$. Any two intersect outside $C$;
an intersection in $C$ would give their two indices the common
neighbours $v$ and a point of $C$, contrary to $C_4$-freeness.
There are at least $q+1-a$ such lines, and each has at most $a$
points outside $C$. Since $q-a>a(a-1)$, the pencil lemma
(Lemma~\ref{struct:bounded-pencil}) makes them concurrent
at a point $p_v$ outside $C$.
If $p_v=p_w$ for distinct $v,w\in V_0\setminus C$, their two
families would be contained in a pencil of $q+1$ lines, while
having at most one common line. This would imply
$2(q+1-a)-1\le q+1$, contrary to our bound on $q$.
Thus all $N-s$ old vertices have distinct point images.
Let $Q$ consist of the $s$ remaining plane points.

For $u\in C$, the $q+1$ distinct images of its neighbours
exhaust $\ell_u$. Hence $\ell_u$ avoids $Q$, and its incidences
with all old points are exactly the adjacencies at $u$.

We first prove symmetry on old points:
\begin{equation}
 p_v\in\ell_w\quad\Longleftrightarrow\quad p_w\in\ell_v.
 \label{geo:old-incidence-symmetry}
\end{equation}
The claim holds if either index is in $C$.
Otherwise put $A_v=N_F(v)\cap C$ and $A_w=N_F(w)\cap C$.
The incidence $p_v\in\ell_w$ implies
that there is no edge between $A_v$ and $A_w$: all lines
$\ell_u$, $u\in A_v$, meet $\ell_w$ at $p_v\notin C$.
Conversely, if there is no such edge and $p_v\notin\ell_w$,
those at least $q+1-a$ lines have distinct intersections with
$\ell_w$, all outside $C$. This contradicts the bound $a$
on the number of outside points. The absence-of-edges condition
is symmetric, proving \eqref{geo:old-incidence-symmetry}.
For an edge $vw$ of $F$ with $v,w\notin C$, an edge between
$A_v$ and $A_w$ would produce a four-cycle. Thus every old
edge is respected by the incidence assignment.

We now have $N-s$ distinct old points and $N-s$ distinct old
lines with symmetric incidences. Since $q\ge2s$,
Lemma~\ref{geo:gram-polarity-extension} extends this assignment
to a unique polarity of the plane. The old-edge conclusion
proved above gives $F\subseteq H-Q$.
\end{proof}


\Needspace{18\baselineskip}
\subsection{Recognition from full-degree vertices}

\begin{theorem}[Intrinsic recognition across any fixed deficient order]
\label{inc:intrinsic-many-full-recognition}
Fix integers $s\ge1$ and $t\ge0$.  For all sufficiently large integers
$q$, let $F$ be a $C_4$-free graph on $N-s=q^2+q+1-s$ vertices.
If at least
\begin{equation}
 N-s(q+1)+\binom{s}{2}-t
 \label{inc:many-full-threshold}
\end{equation}
vertices have degree exactly $q+1$, then there is a polarity graph
$H$ of a projective plane of order $q$ and a set $Q$ of $s$ points
such that $F$ is a spanning subgraph of $H-Q$.
No maximum-degree assumption and no uncovered-pair assumption is
needed.  In particular the conclusion forces $\Delta(F)\le q+1$.
\end{theorem}

\begin{proof}
Choose exactly the number in \eqref{inc:many-full-threshold}
of degree-$(q+1)$ vertices, and call their set $C$.
Take $C$ as the point set and $N_F(v)\cap C$, indexed by all
$v\in V(F)$, as the lines.  Point degrees are $q+1$, and
$C_4$-freeness gives the two intersection conditions for a partial
linear space.  Put $K=s+t$.
Lemma~\ref{inc:general-packing} gives
\[
 r_v:=|N_F(v)\cap C|\ge q+1-K
 \quad\hbox{and hence}\quad
 \delta_v:=q+1-d_F(v)\le K
 \qquad(v\in V(F)).
\]
The deficits may be negative; no nonnegativity is used.
For $x\in C$, there are at most $K$ neighbours outside $C$,
and all neighbours inside $C$ have deficit zero.  Consequently
\[
 a_x:=\sum_{v\in N_F(x)}\delta_v\le K^2.
\]
Counting length-two paths from this full-degree vertex in the
$N-s$ vertex graph gives the exact identity $u_x=a_x-s$.
Thus the uncovered-pair graph restricted to $C$ has maximum degree
at most $K^2$.
Theorem~\ref{inc:fixed-parameter-completion}, with $D=K^2$,
embeds the complete indexed incidence system in a projective plane
of order $q$, with exact incidences.
For $q>(s+t+2)^2$, the polarity-extension lemma
(Lemma~\ref{geo:bounded-polarity-extension}) now applies to
$F,C$ with these same parameters.  It supplies the claimed graph
$H$ and omitted set $Q$.
\end{proof}


\clearpage
\phantomsection
\addcontentsline{toc}{section}{References}
\begin{thebibliography}{10}

\bibitem{Beutelspacher1990}
A.~Beutelspacher.
\newblock Linear spaces: history and theory.
\newblock {\em Le Matematiche}, 45(1):25--38, 1990.
\newblock Theorem~2.2.1.
  \href{https://lematematiche.dmi.unict.it/index.php/lematematiche/article/download/657/625}{Published
  article}.

\bibitem{BeutelspacherMetsch1987}
A.~Beutelspacher and K.~Metsch.
\newblock Embedding finite linear spaces in projective planes, {II}.
\newblock {\em Discrete Mathematics}, 66(3):219--230, 1987.
\newblock
  \href{https://doi.org/10.1016/0012-365X(87)90098-7}{doi:10.1016/0012-365X(87)90098-7}.

\bibitem{Bruen1970}
A.~A. Bruen.
\newblock Baer subplanes and blocking sets.
\newblock {\em Bulletin of the American Mathematical Society}, 76:342--344,
  1970.
\newblock
  \href{https://doi.org/10.1090/S0002-9904-1970-12470-3}{doi:10.1090/S0002-9904-1970-12470-3}.

\bibitem{ErdosSimonovits1983}
P.~Erd{\H{o}}s and M.~Simonovits.
\newblock Supersaturated graphs and hypergraphs.
\newblock {\em Combinatorica}, 3(2):181--192, 1983.
\newblock \href{https://doi.org/10.1007/BF02579292}{doi:10.1007/BF02579292}.

\bibitem{ErdosSimonovits1984}
P.~Erd{\H{o}}s and M.~Simonovits.
\newblock Cube-supersaturated graphs and related problems.
\newblock In {\em Progress in Graph Theory (Waterloo, Ont., 1982)}, pages
  203--218. Academic Press, Toronto, ON, 1984.
\newblock \href{https://users.renyi.hu/~p_erdos/1984-04.pdf}{Published
  chapter}.

\bibitem{FirkeEtAl2013}
F.~A. Firke, P.~M. Kosek, E.~D. Nash, and J.~Williford.
\newblock Extremal graphs without 4-cycles.
\newblock {\em Journal of Combinatorial Theory, Series B}, 103(3):327--336,
  2013.
\newblock
  \href{https://doi.org/10.1016/j.jctb.2013.01.001}{doi:10.1016/j.jctb.2013.01.001}.

\bibitem{Furedi1983}
Z.~F{\"u}redi.
\newblock Graphs without quadrilaterals.
\newblock {\em Journal of Combinatorial Theory, Series B}, 34(2):187--190,
  1983.
\newblock
  \href{https://doi.org/10.1016/0095-8956(83)90018-7}{doi:10.1016/0095-8956(83)90018-7}.

\bibitem{HeMaYang2021}
J.~He, J.~Ma, and T.~Yang.
\newblock Some extremal results on 4-cycles.
\newblock {\em Journal of Combinatorial Theory, Series B}, 149:92--108, 2021.
\newblock
  \href{https://doi.org/10.1016/j.jctb.2021.01.007}{doi:10.1016/j.jctb.2021.01.007}.

\bibitem{HeMaYang2023}
J.~He, J.~Ma, and T.~Yang.
\newblock Some exact results on 4-cycles: stability and supersaturation.
\newblock {\em CSIAM Transactions on Applied Mathematics}, 4(1):74--128, 2023.
\newblock
  \href{https://doi.org/10.4208/csiam-am.SO-2021-0006}{doi:10.4208/csiam-am.SO-2021-0006}.

\bibitem{Kivva2021Spectral}
B.~Kivva.
\newblock On the spectral gap and the automorphism group of distance-regular
  graphs.
\newblock {\em Journal of Combinatorial Theory, Series B}, 149:161--197, 2021.
\newblock Theorem~2.7.
  \href{https://math.uchicago.edu/~bkivva/files/articles/drg-spectral-gap.pdf}{Published
  version}.

\bibitem{MaYang2023}
J.~Ma and T.~Yang.
\newblock Upper bounds on the extremal number of the 4-cycle.
\newblock {\em Bulletin of the London Mathematical Society}, 55(4):1655--1667,
  2023.
\newblock \href{https://doi.org/10.1112/blms.12810}{doi:10.1112/blms.12810}.

\bibitem{Metsch1995Grassmann}
K.~Metsch.
\newblock A characterization of {Grassmann} graphs.
\newblock {\em European Journal of Combinatorics}, 16(6):639--644, 1995.
\newblock Result~2.2.
  \href{https://doi.org/10.1016/0195-6698(95)90045-4}{doi:10.1016/0195-6698(95)90045-4}.

\end{thebibliography}
\end{document}