64c3814
==== TABLE OF CONTENTS ====
A-proof-of-Seymours-second-neighborhood-conjecture//00-introduction.tex
A-proof-of-Seymours-second-neighborhood-conjecture//01-reduction.tex
A-proof-of-Seymours-second-neighborhood-conjecture//02-pruning.tex
A-proof-of-Seymours-second-neighborhood-conjecture//03-incompatibility.tex
A-proof-of-Seymours-second-neighborhood-conjecture//04-weighted-consequences.tex
A-proof-of-Seymours-second-neighborhood-conjecture//05-directed-cycle-consequences.tex
A-proof-of-Seymours-second-neighborhood-conjecture//main.tex
A-proof-of-Seymours-second-neighborhood-conjecture//pruning.tex
A-proof-of-Seymours-second-neighborhood-conjecture//references.bib
===========================
==== BEGIN A-proof-of-Seymours-second-neighborhood-conjecture//00-introduction.tex ====
\section{Introduction}\label{sec:introduction}
An \emph{oriented graph} is a finite directed graph with no loops, no multiple
arcs, and no pair of opposite arcs. Its underlying undirected graph need
not be complete or connected. For a vertex \(v\), write
\[
N_1^+(v)=\{u:v\to u\},\qquad
N_2^+(v)=\{w\notin\{v\}\cup N_1^+(v):
\text{ there is a vertex }u\text{ with }v\to u\to w\}.
\]
Thus \(N_2^+(v)\) consists of the vertices at directed distance exactly two
from \(v\). Each vertex is counted once, regardless of the number of paths
reaching it. Seymour's second neighborhood conjecture asserts that some
vertex satisfies \(\abs{N_1^+(v)}\leq\abs{N_2^+(v)}\).
\begin{theorem}\label{thm:main}
Every nonempty finite oriented graph has a vertex \(v\) such that
\[
\abs{N_1^+(v)}\leq \abs{N_2^+(v)}.
\]
\end{theorem}
Theorem~\ref{thm:main} resolves the conjecture positively, without a
connectivity or degree hypothesis. In particular, a sink already satisfies
the conclusion. The conjecture is a basic comparison between the first two
out-neighborhoods: removing vertices already reached in one step is essential
to its assertion.
The theorem also gives the established vertex- and arc-weighted forms of
the conjecture through Seacrest's equivalences~\cite{Seacrest2015}.
The vertex-weighted conclusions have two different quantifier orders:
for every nonnegative weighting there is a suitable vertex, and there is
a weighting of total mass one for which every vertex is suitable.
Section~\ref{sec:weighted-consequences} states these forms precisely.
Section~\ref{sec:directed-cycle-consequences} records consequences for
short directed cycles. In particular, a graph with minimum in- and
outdegree at least one third of its order contains a directed triangle.
The conjecture was recorded by Dean and Latka~\cite{DeanLatka1995}.
A \emph{tournament} is an oriented graph with an arc between every pair of
distinct vertices. This case, also known as Dean's conjecture, was proved
by Fisher~\cite{Fisher1996} using a probability distribution obtained from
Farkas' lemma. Havet and Thomass\'e gave a combinatorial proof using
local median orders~\cite{HavetThomasse2000}. Fidler and
Yuster~\cite{FidlerYuster2007} extended the tournament theorem to
tournaments missing a matching, a star, or a clique. Ghazal corrected the
star-case proof and treated generalized stars~\cite{Ghazal2012}.
Subsequent advances include a matching together with a
star~\cite{DaraFrancisJacobNarayanan2022} and two
stars~\cite{DaamouchAlMninyGhazal2025}.
Other approaches impose degree conditions or weaken the desired ratio.
Kaneko and Locke established the conjecture for minimum outdegree at most
six~\cite{KanekoLocke2001}; a recent computer-assisted preprint treats
minimum outdegree seven~\cite{SadhukhanSandeepSen2026}.
Chen, Shen and Yuster proved a universal second-to-first neighborhood
ratio of approximately $0.657298$~\cite{ChenShenYuster2003}.
Huang and Peng raise this to approximately $0.715538$ and additionally
report a computational bound of $0.74530$~\cite{HuangPeng2024}.
Botler, Moura and Naia~\cite{BotlerMouraNaia2023}, followed by
Espuny D\'iaz, Gir\~ao, Granet and Kronenberg~\cite{EspunyDiazEtAl2025},
studied every orientation of binomial random graphs; the latter result
covers every fixed edge probability below $1/2$, with probability tending
to one as the order tends to infinity. Brukhman's recent dense-case
preprint concerns graphs of order $n\leq 2\delta+2$, where $\delta$ is
the minimum outdegree~\cite{Brukhman2026}.
Our proof builds on the minimal-counterexample and graph-product
methods of Brantner, Brockman, Kay and
Snively~\cite{BrantnerBrockmanKaySnively2009} and on Seacrest's
subset perspective~\cite{Seacrest2019}.
We adapt the edge-deletion idea in the proof of Seacrest's Lemma~4 to
obtain the stronger subset inequality needed here, and give that argument
in full. The exact set-image convention and inequality are stated below.
The main additional ingredient is a pruning bound for arbitrary finite
binary relations. Its deletion cost depends on the points left uncovered
after pruning; this dependence makes the final extremal argument possible.
\paragraph{Proof strategy.}
For a digraph \(D\) and a set \(S\) of its vertices, define
\[
F_D(S)=\{y:\text{ there is }x\in S\text{ with }x\to y\},
\qquad F_D^2(S)=F_D(F_D(S)).
\]
The operator \(F_D\) does not subtract \(S\). In an oriented graph there is
no directed walk of length two from a vertex to itself, and hence
\(N_2^+(v)=F_D^2(\{v\})\setminus F_D(\{v\})\).
We first suppose that a counterexample exists and choose one with minimum
order and then minimum number of arcs. Deleting carefully chosen arcs
shows that every nonempty proper vertex set \(S\) satisfies
\[
\abs{F_D^2(S)\setminus F_D(S)}
<
\abs{F_D(S)\setminus S}.
\]
Replacing each vertex by a sufficiently large transitive tournament turns
this into a strict inequality
\begin{equation}\label{eq:overview-concavity}
\abs{U}+\abs{F_G^2(U)}<2\abs{F_G(U)}
\end{equation}
for every nonempty proper subset \(U\) of the new oriented graph \(G\).
Every vertex of \(G\) has positive indegree. These reductions are proved in
Section~\ref{sec:reduction}.
The obstruction to~\eqref{eq:overview-concavity} is an extremal argument
on two families of ordered pairs in $V(G)\times V(G)$. A coordinate image
advances that coordinate along an arc of $G$ and leaves the other coordinate
fixed. The families are compatible when the first-coordinate image of the left family and the
second-coordinate image of the right family are disjoint. A point in
neither image is called uncovered. Require both families to contain the
diagonal, write $M$ for their combined size and $d$ for the number of
uncovered points, and maximize $M+d$ over all such compatible pairs.
The columns of the left family and the rows of the right family are
nonempty proper vertex sets, so
\eqref{eq:overview-concavity} applies to each of them. Taking complements
of the second iterated images then produces prospective families with
combined size greater than $M+2d$.
These families may conflict, but their diagonal members are still present
and conflict-free. The pruning lemma in
Section~\ref{sec:pruning}, valid for every finite binary relation,
restores compatibility and preserves their diagonal members.
In this application its two deletion-cost terms are at most $d$ and $d'$,
where $d'$ is the number of points left uncovered by the retained families.
Thus at most $d+d'$ members are deleted, and the new extremal objective is
strictly greater than
\[
M+2d-(d+d')+d'=M+d.
\]
Section~\ref{sec:incompatibility} proves these bounds and obtains the
contradiction. This is why the pruning lemma must charge part of its
cost to the points left uncovered after deletion.
The pruning proof bounds a matching in an augmented bipartite graph.
Changing the two coordinates of a pair in opposite orders factors the
same matrix through two different index sets attached to a conflict.
A simultaneous maximum-rank choice of the entries makes the kernels of
these maps control the matching size. The full argument is independent
of the orientation assumption and is given in Section~\ref{sec:pruning}.
==== END A-proof-of-Seymours-second-neighborhood-conjecture//00-introduction.tex ====
==== BEGIN A-proof-of-Seymours-second-neighborhood-conjecture//01-reduction.tex ====
\section{From a counterexample to a strict subset inequality}
\label{sec:reduction}
We first convert a hypothetical counterexample into a graph whose first
image is larger than the average of a set and its second image. Throughout
this section, $F=F_D$ denotes the ordinary union of the out-neighborhoods
in a specified base graph $D$; in particular, $F(S)$ need not be disjoint
from $S$.
\begin{proposition}[Counterexample reduction]
\label{prop:counterexample-reduction}
If Theorem~\ref{thm:main} has a counterexample, then there is a finite
nonempty oriented graph $G$ in which every vertex has positive indegree
and
\begin{equation}
\label{eq:strict-subset-growth}
\abs{U}+\abs{F_G^2(U)}<2\abs{F_G(U)}
\qquad\text{for every }\varnothing\ne U\subsetneq V(G).
\end{equation}
\end{proposition}
There are two steps. Minimality first gives a strict deficit for subsets
of a counterexample. Replacing each vertex by a sufficiently large
transitive tournament then turns that deficit into
\eqref{eq:strict-subset-growth}.
The arc-deletion argument below adapts the proof idea of
\cite[Lemma~4]{Seacrest2019}. Specializing Seacrest's parameter $\lambda$
to $1$, his statement gives
$\abs{F^2(S)\setminus F(S)}<\abs{F(S)}$ in an edge-minimal
counterexample when $F(S)$ is nonempty. Lemma~\ref{lem:subset-deficit}
replaces this right-hand bound by $\abs{F(S)\setminus S}$ for nonempty
proper $S$, under the stronger choice of minimum order and then minimum
arc count. We prove this strengthened form in full.
\begin{lemma}[Subset deficit]
\label{lem:subset-deficit}
Let $D$ be a finite nonempty oriented graph such that
$\abs{N_1^+(v)}>\abs{N_2^+(v)}$ for every $v\in V(D)$.
Choose $D$ with minimum order and, subject to that, minimum number of
arcs among all graphs with this property. Then $D$ is strongly connected,
every vertex has positive indegree, and
\begin{equation}
\label{eq:subset-deficit}
\abs{F^2(S)\setminus F(S)}<\abs{F(S)\setminus S}
\qquad\text{for every }\varnothing\ne S\subsetneq V(D).
\end{equation}
\end{lemma}
\begin{proof}
A sink satisfies the second-neighborhood inequality, so $D$ has no sink
and has more than one vertex. If $D$ were not strongly connected, take
a strongly connected component with no outgoing arc to another component.
All first and second out-neighborhoods of its vertices lie in that
component. Its induced graph would therefore be a smaller counterexample,
contrary to the choice of $D$. Thus $D$ is strongly connected, and every
vertex has an in-neighbor.
Fix a nonempty proper subset $S$ and put
\[
I=F(S)\cap S,\qquad E=F(S)\setminus S,
\qquad g(T)=\abs{F(T)\setminus(I\cup T)}\quad(T\subseteq E).
\]
Strong connectivity gives $E\ne\varnothing$. We will enlarge $T$ from
$\varnothing$ to $E$ so that the increase in $g(T)$ is strictly smaller
than the number of newly adjoined vertices at every step.
For $T\subsetneq E$, let $D_T$ be obtained from the original graph $D$
by deleting all arcs from $S$ to $E\setminus T$. Since every vertex of
$E\setminus T$ receives an arc from $S$, at least one arc is deleted.
Minimality of the number of arcs gives a vertex $v$ satisfying
$\abs{N_{1,D_T}^+(v)}\le\abs{N_{2,D_T}^+(v)}$.
If $v$ had lost no first out-neighbor, deleting arcs could only shrink
its exact second out-neighborhood, so it would still violate this
inequality. Consequently $v\in S$, and the set
\[
Q=F(\{v\})\cap(E\setminus T)
\]
is nonempty. It is exactly the set of first out-neighbors that $v$ loses.
The original first out-neighborhood of $v$ is contained in $I\cup T\cup Q$,
and the remaining first out-neighbors lie in $I\cup T$.
We compare the exact second out-neighborhoods before and after deletion.
A two-step path from $v$ in $D_T$ through a vertex of $I\subseteq S$
ends in $I\cup T$, since all arcs from $S$ to $E\setminus T$ were
deleted. A path through a vertex of $T$ ends in $F(T)$. Thus
\begin{equation}
\label{eq:deleted-path-endpoints}
F_{D_T}^2(\{v\})\subseteq I\cup T\cup F(T).
\end{equation}
Every newly counted exact second out-neighbor must have been a first
out-neighbor in $D$: deletion creates no paths, and $v$ itself is never
an exact second out-neighbor. Such a vertex lies in $Q$, and
\eqref{eq:deleted-path-endpoints}, together with
$Q\cap(I\cup T)=\varnothing$, places it in $Q\cap F(T)$.
On the other hand, define
\[
C=F(Q)\setminus\bigl(I\cup T\cup Q\cup F(T)\bigr).
\]
Every vertex of $C$ was reached from $v$ in two steps through $Q$, and
none was a first out-neighbor. Also $v\notin F(Q)$: an arc from a
vertex of $Q$ back to $v$ would oppose the arc from $v$ to that vertex.
Hence $C\subseteq N_{2,D}^+(v)$. By
\eqref{eq:deleted-path-endpoints}, no vertex of $C$ remains reachable
in two steps in $D_T$.
Write $d_1=\abs{N_{1,D}^+(v)}$ and
$d_2=\abs{N_{2,D}^+(v)}$. The gains and losses just identified imply
\[
d_1-\abs{Q}
\le \abs{N_{2,D_T}^+(v)}
\le d_2-\abs{C}+\abs{Q\cap F(T)}.
\]
The change in $g$ is exact: adjoining $Q$ removes the points
$Q\cap F(T)$ from the previously counted image and adds precisely $C$.
Since $d_2<d_1$, it follows that
\begin{equation}
\label{eq:deficit-increment}
g(T\cup Q)-g(T)
=\abs{C}-\abs{Q\cap F(T)}
\le \abs{Q}+d_2-d_1
<\abs{Q}.
\end{equation}
Starting with $T=\varnothing$, repeat this step until $T=E$.
Each deletion is performed afresh on the original $D$, so the same
minimality argument applies at every step. Each $Q$ is a nonempty
subset of the part of $E$ not yet adjoined; hence the process terminates.
Summing \eqref{eq:deficit-increment} and using $g(\varnothing)=0$
gives $g(E)<\abs{E}$. Finally,
$F(S)=I\cup E$ and $F(I)\subseteq F(S)$, so
\[
F^2(S)\setminus F(S)
=\bigl(F(I)\cup F(E)\bigr)\setminus(I\cup E)
=F(E)\setminus(I\cup E).
\]
Its cardinality is $g(E)$, proving \eqref{eq:subset-deficit}.
\end{proof}
We next amplify the integer deficit in \eqref{eq:subset-deficit}.
Each unit of the base deficit contributes the entire block size; the
remaining internal contribution costs at most one unit per base vertex.
The construction below is the lexicographic product $D[T_m]$, where $T_m$
is a transitive tournament. The same graph-product construction appears
in \cite[Theorem~4.3]{BrantnerBrockmanKaySnively2009}; here we need an
estimate for every nonempty proper subset, rather than only for individual
vertices.
\begin{lemma}[Transitive-tournament blowup]
\label{lem:blowup}
Let $D$ be an oriented graph on $n\ge1$ vertices, all of positive
indegree, satisfying \eqref{eq:subset-deficit} for every nonempty proper
subset of $V(D)$. For an integer $m>n$, replace each vertex by a
transitive tournament on $m$ vertices. For every arc $v\to w$ of $D$,
put all arcs from the block at $v$ to the block at $w$, and put no other
arcs between distinct blocks. The resulting graph $G$ is oriented,
all its indegrees are positive, and it satisfies
\eqref{eq:strict-subset-growth}.
\end{lemma}
\begin{proof}
Label the vertices within each block by $1,\ldots,m$, with arcs from
smaller to larger labels. Let $f$ be the image operator within this
transitive tournament. For a nonempty set $T$ of labels with least
element $a$, we have $f(T)=\{a+1,\ldots,m\}$. Thus
\begin{equation}
\label{eq:internal-block-bound}
\abs{T}-\abs{f(T)}\le1,\qquad
f^2(T)\subseteq f(T),\qquad
\abs{T}-2\abs{f(T)}+\abs{f^2(T)}\le1.
\end{equation}
The construction produces an oriented graph. Every vertex receives
arcs from an incoming base block, so all indegrees in $G$ are positive.
Call an arc external if it joins distinct blocks, and internal otherwise.
Fix $\varnothing\ne U\subsetneq V(G)$. Write $T_v$ for the labels
selected by $U$ in the block at $v$, and define its support and a set
of base vertices by
\[
S=\{v\in V(D):T_v\ne\varnothing\},\qquad
H_0=F(S)\cup F^2(S).
\]
Every block indexed by $F(S)$ is filled by $F_G(U)$. In each remaining
block the first image consists exactly of $f(T_v)$, so
\[
\abs{F_G(U)}=m\abs{F(S)}
+\sum_{v\in S\setminus F(S)}\abs{f(T_v)}.
\]
A two-step path using two external arcs ends in an $F^2(S)$-block.
One using exactly one external arc ends in an $F(S)$-block, regardless
of the order of its internal and external steps. Paths using only
internal arcs contribute $f^2(T_v)$. Therefore
\[
\abs{F_G^2(U)}\le m\abs{H_0}
+\sum_{v\in S\setminus H_0}\abs{f^2(T_v)}.
\]
Combining these estimates gives the sharper bound
\begin{align}
\label{eq:blowup-sharp}
\abs{U}-2\abs{F_G(U)}+\abs{F_G^2(U)}
&\le m\bigl(\abs{H_0}-2\abs{F(S)}\bigr)
+\sum_{v\in S}\abs{T_v} \notag\\
&\quad -2\sum_{v\in S\setminus F(S)}\abs{f(T_v)}
+\sum_{v\in S\setminus H_0}\abs{f^2(T_v)}.
\end{align}
Since $F(S)\subseteq H_0$, extending the last sum to
$S\setminus F(S)$ only adds nonnegative terms. This may count internal
second images in blocks already bounded by a full block in
\eqref{eq:blowup-sharp}; it remains a valid upper bound. Now use
$\abs{T_v}\le m$ on $S\cap F(S)$ and
\eqref{eq:internal-block-bound} on $S\setminus F(S)$ to obtain
\begin{align*}
\abs{U}-2\abs{F_G(U)}+\abs{F_G^2(U)}
&\le m\bigl(\abs{H_0}-2\abs{F(S)}
+\abs{S\cap F(S)}\bigr)
+\abs{S\setminus F(S)}\\
&\le m\bigl(\abs{F^2(S)\setminus F(S)}
-\abs{F(S)\setminus S}\bigr)+n.
\end{align*}
If $S\subsetneq V(D)$, the parenthesized difference is an integer
strictly less than zero by \eqref{eq:subset-deficit}. The last bound
is consequently at most $-m+n<0$.
It remains to consider $S=V(D)$, for which the subset-deficit hypothesis
does not apply. Positive indegrees in $D$ give $F(S)=V(D)$, so
$F_G(U)=V(G)$. Positive indegrees in $G$ then give
$F_G^2(U)=V(G)$ as well. In this case
\[
\abs{U}-2\abs{F_G(U)}+\abs{F_G^2(U)}
=\abs{U}-\abs{V(G)}<0,
\]
because $U$ is proper. This proves the required inequality for every
allowed $U$.
\end{proof}
\begin{proof}[Proof of Proposition~\ref{prop:counterexample-reduction}]
Choose a counterexample of minimum order and then minimum number of
arcs. Lemma~\ref{lem:subset-deficit} supplies positive indegrees and
the subset deficit, so Lemma~\ref{lem:blowup}, with any integer
$m>\abs{V(D)}$, supplies the required graph $G$.
\end{proof}
==== END A-proof-of-Seymours-second-neighborhood-conjecture//01-reduction.tex ====
==== BEGIN A-proof-of-Seymours-second-neighborhood-conjecture//02-pruning.tex ====
\section{Pruning two families of pairs}\label{sec:pruning}
We now prove a deletion bound for two families of ordered pairs. The bound
charges the deleted members to two sets of pairs: one determined by the
original conflicts, and the other consisting of points left uncovered after
deletion. This dependence on the surviving families will be essential in
Section~\ref{sec:incompatibility}. The result holds for every finite binary
relation; no orientation assumption is needed.
\begin{lemma}[Pruning]\label{lem:pruning}
Let $X$ be a finite set with a binary relation denoted by $\to$, and let
$\mathcal R,\mathcal C\subseteq X\times X$ be two families, regarded as
separate copies even when their coordinates agree. Say that
$(p,j)\in\mathcal R$ and $(i,s)\in\mathcal C$ \emph{conflict} if
\[
p\to i\qquad\text{and}\qquad s\to j.
\]
Define
\begin{align*}
Z&=\{(i,j):\text{some }(p,j)\in\mathcal R
\text{ conflicts with some }(i,s)\in\mathcal C\},\\
H&=\{(p,s):\text{some }(p,j)\in\mathcal R
\text{ conflicts with some }(i,s)\in\mathcal C\}.
\end{align*}
A point $(i,j)$ is \emph{covered} by a member $(p,j)\in\mathcal R$ when
$p\to i$, and by a member $(i,s)\in\mathcal C$ when $s\to j$.
These are the only ways a member covers a point.
There are subfamilies $\mathcal R'\subseteq\mathcal R$ and
$\mathcal C'\subseteq\mathcal C$ with no conflicts between them such that
every initially conflict-free member is retained and
\begin{equation}\label{eq:pruning-bound}
\abs{\mathcal R\setminus\mathcal R'}+
\abs{\mathcal C\setminus\mathcal C'}
\leq \abs H+
\abs{\{z\in Z:z\text{ is covered by no member of }
\mathcal R'\cup\mathcal C'\}}.
\end{equation}
The two sides are counted separately throughout.
\end{lemma}
The proof will bound a matching in an augmented bipartite graph by using
matrix ranks. We first record the elementary rank fact that makes the
argument work. For finite index sets $I,J$, a matrix supported on
$T\subseteq I\times J$ means a real matrix whose entries outside $T$ are
zero; entries in $T$ are allowed to vanish.
\begin{lemma}[Kernels at maximum support rank]\label{lem:kernel-support}
Let $T\subseteq I\times J$, where $I$ and $J$ are finite. Suppose that
$D:\R^J\to\R^I$ has maximum rank among all real matrices supported on $T$.
Then, for every $x\in\ker D$, every $y\in\ker D^{\mathsf T}$, and every
$(s,j)\in T$, one has $x_jy_s=0$.
\end{lemma}
\begin{proof}
Suppose instead that $x_jy_s\ne0$. For a nonzero real $\tau$, the matrix
$D_\tau=D+\tau e_s e_j^{\mathsf T}$ is still supported on $T$, and
\[
D_\tau x=\tau x_j e_s.
\]
Thus $e_s\in\im D_\tau$. Moreover, for every $w\in\R^J$,
\[
Dw=D_\tau w-\tau w_j e_s\in\im D_\tau,
\]
so the entire old image $\im D$ is contained in $\im D_\tau$.
On the other hand, $y$ annihilates $\im D$ and $y_s\ne0$, so
$e_s\notin\im D$. Therefore $\rank D_\tau>\rank D$, a contradiction.
\end{proof}
\begin{proof}[Proof of Lemma~\ref{lem:pruning}]
If there are no conflicts, retain every member; then $Z=H=\varnothing$
and the assertion is immediate. In what follows, all vector spaces have
their usual coordinate bases. Empty minors have determinant $1$, so the
rank arguments also apply when a matching or an index set is empty.
\medskip\noindent
\emph{The augmented graph and the required matching bound.}
Form a bipartite graph $\Gamma$ with parts
\[
\mathcal V_L=\mathcal R\sqcup Z_L,
\qquad
\mathcal V_R=\mathcal C\sqcup Z_R,
\]
where $Z_L$ and $Z_R$ are separate copies of $Z$, disjoint also from the
two original families. Join conflicting original members. Also join
each original member to the opposite copy of every point of $Z$ that it
covers. There are no edges between $Z_L$ and $Z_R$.
Figure~\ref{fig:pruning} displays the three edges forced by one conflict.
\begin{figure}[!ht]
\centering
\input{figures/pruning.tex}
\caption{A conflict between $r=(p,j)$ and $c=(i,s)$ forces this path,
where $z=(i,j)\in Z$. The copies $z_L$ and $z_R$ are distinct vertices.
The vertices alternate between the two sides of the bipartition.
Different conflicts can share vertices and edges; the full augmented
graph need not be a disjoint union of such paths.}
\label{fig:pruning}
\end{figure}
An initially conflict-free member is isolated in $\Gamma$.
Indeed, if $(p,j)\in\mathcal R$ covered $(i,j)\in Z$, an original
conflict witnessing $(i,j)\in Z$ would supply a member
$(i,s)\in\mathcal C$ with $s\to j$. This member would conflict with
$(p,j)$. The same argument with the sides exchanged applies to
$\mathcal C$.
It suffices to find a vertex cover $K$ of $\Gamma$ of size at most
$\abs Z+\abs H$, omitting isolated vertices. Delete precisely its
original members. No conflict then survives. If $q$ points of $Z$ are
uncovered by the surviving members, each of the other $\abs Z-q$ points
has a surviving member adjacent to one of its two copies. That copy
must lie in $K$. Distinct points require distinct new vertices, whence
\begin{equation}\label{eq:cover-charge}
\abs{K\cap(\mathcal R\sqcup\mathcal C)}
\leq \abs K-(\abs Z-q)\leq\abs H+q.
\end{equation}
Thus the cover gives exactly~\eqref{eq:pruning-bound} and retains every
initially conflict-free member.
We will obtain this cover by proving that a maximum matching in $\Gamma$
has size at most $\abs Z+\abs H$ and then giving the usual alternating-path
construction of the cover. Choose a maximum matching $\mathcal M$ with
the fewest edges between original members. Write $k$ for the number of
these edges, and let $\alpha$ and $\beta$ be its edges in
$\mathcal R\times Z_R$ and $Z_L\times\mathcal C$, respectively. Put
\[
\ell=\abs\alpha,\qquad t=\abs\beta,
\qquad\abs{\mathcal M}=k+\ell+t.
\]
Each of $\alpha$ and $\beta$ is a maximum matching in its own subgraph.
For example, if the $\mathcal R$--$Z_R$ subgraph had a larger matching,
its symmetric difference with $\alpha$ would contain an
$\alpha$-augmenting path, starting at an $\alpha$-unmatched member of
$\mathcal R$ and ending at an $\alpha$-unmatched vertex of $Z_R$.
The latter vertex is unmatched in $\mathcal M$, and every internal vertex
of the path is matched by $\alpha$. If the starting member is unmatched
in $\mathcal M$, augmenting gives a larger matching in $\Gamma$.
Otherwise it lies on an original--original edge of $\mathcal M$;
remove that edge and augment along the path. This preserves the total
size and reduces $k$. Both conclusions contradict the choice of
$\mathcal M$. The proof for $\beta$ is identical with the sides
exchanged. Denote by $R_\alpha\subseteq\mathcal R$ and
$C_\beta\subseteq\mathcal C$ the original vertices matched by these
two matchings.
\medskip\noindent
\emph{Four maps and a simultaneous choice of coefficients.}
To bound $k+\ell+t$, we encode the two maximum matchings by matrix ranks.
For each arrow $x\to y$, introduce independent variables $a_{xy}$ and
$b_{xy}$, with the two arrays independent of one another. Set both
entries to zero when $x\not\to y$. We shall choose real values for all
the variables shortly. For any real assignment, define four maps by
\[
\begin{array}{ccc}
\R^{\mathcal R}&\xrightarrow{\ L\ }&\R^Z\\[3pt]
{\scriptstyle B}\big\downarrow&&\big\downarrow{\scriptstyle N}\\[3pt]
\R^H&\xrightarrow{\ A\ }&\R^{\mathcal C}
\end{array}
\]
with entries
\begin{equation}\label{eq:pruning-maps}
\begin{aligned}
L_{(i,j),(p,j)}&=a_{pi},&
N_{(i,s),(i,j)}&=b_{sj},\\
B_{(p,s),(p,j)}&=b_{sj},&
A_{(i,s),(p,s)}&=a_{pi}.
\end{aligned}
\end{equation}
The row and column indices in each formula range over its indicated
coordinate sets, and every entry not of a listed form is zero.
The maps $L,A$ change the first coordinate forward along $p\to i$;
$N,B$ change the second coordinate backward from $j$ to $s$ along $s\to j$.
For a conflict, the two routes from $(p,j)$ to $(i,s)$ change the
coordinates in opposite orders, through $(i,j)\in Z$ or $(p,s)\in H$.
For a fixed column $(p,j)\in\mathcal R$ and row
$(i,s)\in\mathcal C$, the only possible intermediate index in $NL$ is
$(i,j)$, and the only possible one in $AB$ is $(p,s)$. If the two
endpoints conflict, these indices belong to $Z$ and $H$, respectively,
and both products have entry $a_{pi}b_{sj}$. If they do not conflict,
at least one factor is zero in both products. Hence
\begin{equation}\label{eq:pruning-commute}
NL=AB.
\end{equation}
We seek an assignment for which
\[
\rank L=\ell,\qquad \rank N=t,\qquad \dim\ker A\geq k.
\]
These three conditions give the desired matching bound. Indeed,
rank--nullity and $NL=AB$ would give
\begin{align}
\abs H
&=\dim\ker A+\rank A\notag\\
&\geq k+\rank A
\geq k+\rank(NL)\notag\\
&\geq k+\ell+t-\abs Z.
\label{eq:pruning-rank-bound}
\end{align}
The last inequality follows by restricting $N$ to $\im L$:
\[
\rank(NL)
=\dim\im L-\dim(\im L\cap\ker N)
\geq\ell-(\abs Z-t).
\]
The first two rank conditions will come from $\alpha$ and $\beta$.
For the third, we will lift the $k$ original left endpoints to vectors
$u^r\in\ker L$ and show that their images $Bu^r$ are independent.
The identity $AB=NL$ places these images in $\ker A$.
Our choice of coefficients uses the correspondence between generic matrix
rank and maximum matching size~\cite[Section~5, Theorem~1]{Edmonds1967}.
We apply the determinant argument within coordinate blocks and verify that
all required minors can be nonzero at the same assignment.
We choose the coefficients so that $\rank L=\ell$, with its
$R_\alpha$ columns a basis of $\im L$, and
$\rank N^{\mathsf T}=t$, with its $C_\beta$ columns a basis of
$\im N^{\mathsf T}$. To justify this choice, a nonzero minor of $L$
requires a matching between its column and row indices: a nonzero term
in its determinant supplies the matching. Since $\alpha$ is maximum,
$\rank L\leq\ell$ for every coefficient assignment. The square minor
using precisely the endpoints of $\alpha$ is, up to row and column
ordering, block diagonal by the second coordinate $j$. In each block
all allowed entries are distinct variables $a_{pi}$. The matching
gives a determinant monomial that cannot cancel, because different
permutations use different sets of these variables. Each block
determinant is therefore a nonzero polynomial, and so is their product.
Variables may occur in more than one block, but a product of nonzero
polynomials remains nonzero. This proves the required independence
when that minor does not vanish. For $N^{\mathsf T}$ the same argument
uses blocks with the first coordinate $i$ fixed and distinct variables
$b_{sj}$ within each block.
One additional finite collection of rank conditions will be needed.
For every arrow $p\to i$, define
\[
J_p=\{j:(p,j)\in\mathcal R\},\qquad
S_i=\{s:(i,s)\in\mathcal C\},\qquad
D^{p,i}=(b_{sj})_{s\in S_i,\ j\in J_p}.
\]
We require $D^{p,i}$ to have maximum rank among all matrices supported
on
\[
T^{p,i}=\{(s,j)\in S_i\times J_p:s\to j\}.
\]
These matrices will let Lemma~\ref{lem:kernel-support} compare restrictions
of vectors in $\ker B$ and $\ker N^{\mathsf T}$.
The allowed entries of each individual $D^{p,i}$ are independent
variables. A minor attaining its maximum possible rank at some
assignment is therefore a nonzero polynomial in the $b$ variables.
Choose one such minor for each arrow, taking the empty minor when the
maximum rank is zero. Multiply these finitely many polynomials with
the two matching minors just described. The product is nonzero in the
polynomial ring generated by all $a$ and $b$ variables, even though
variables are shared between different matrices. A nonzero real
polynomial is nonzero at some real assignment, as follows by induction
on its number of variables. Fix such an assignment once and for all.
It gives these support ranks and the two basis properties simultaneously.
For every edge $(r,c)$ of $\mathcal M$ between original members, the
basis properties now give vectors
\begin{equation}\label{eq:pruning-lifts}
\begin{aligned}
u^r&=e_r+\sum_{a\in R_\alpha}\lambda_a^r e_a
\in\ker L,\\
v^c&=e_c+\sum_{b\in C_\beta}\mu_b^c e_b
\in\ker N^{\mathsf T}.
\end{aligned}
\end{equation}
The original--original endpoints are disjoint from $R_\alpha$ and
$C_\beta$, respectively. In particular, the $u^r$ restrict to distinct
unit vectors on the $k$ original left endpoints, and $v^c_c=1$.
\medskip\noindent
\emph{The kernel restriction and the matching bound.}
It remains to show that the $k$ lifts just constructed give independent
vectors $Bu^r$. The key assertion, at our fixed coefficient assignment, is
\begin{equation}\label{eq:conflict-kernel}
u_{pj}v_{is}=0
\quad\text{for every conflict }((p,j),(i,s)),
\quad u\in\ker B,\quad v\in\ker N^{\mathsf T}.
\end{equation}
Here the assertion quantifies over \emph{all} vectors in the two kernels.
To prove it, fix an arrow $p\to i$. For $u\in\ker B$, consider the
vector $(u_{pj})_{j\in J_p}$. If a row $s\in S_i$ of $D^{p,i}$ has
an allowed entry, choose $j\in J_p$ with $s\to j$. Then
$(p,j)$ and $(i,s)$ conflict, so $(p,s)\in H$. The complete equation
of $Bu=0$ at this coordinate is
\begin{equation}\label{eq:pruning-row-equation}
\sum_{j\in J_p}b_{sj}u_{pj}=0.
\end{equation}
If the row has no allowed entry, this equation holds because all its
coefficients are zero. Thus it holds for every $s\in S_i$, including
rows for which $(p,s)$ is absent from $H$. Consequently
$(u_{pj})_{j\in J_p}\in\ker D^{p,i}$.
Similarly, let $v\in\ker N^{\mathsf T}$. If a column $j\in J_p$
of $D^{p,i}$ has an allowed entry, choose $s\in S_i$ with $s\to j$.
The resulting conflict implies $(i,j)\in Z$, and the complete equation
of $N^{\mathsf T}v=0$ at this coordinate is
\begin{equation}\label{eq:pruning-column-equation}
\sum_{s\in S_i}b_{sj}v_{is}=0.
\end{equation}
Columns with no allowed entries satisfy the same equation
automatically. Hence $(v_{is})_{s\in S_i}\in\ker(D^{p,i})^{\mathsf T}$.
Since $D^{p,i}$ has maximum rank on its allowed support,
Lemma~\ref{lem:kernel-support} gives $u_{pj}v_{is}=0$ whenever
$s\to j$, proving~\eqref{eq:conflict-kernel}.
The hypothetical single-entry perturbation in that lemma concerns only
$D^{p,i}$; it need not preserve any other rank condition. The conclusion
holds for every pair of kernel vectors at the fixed, original assignment.
For each original--original matched edge $(r,c)$, substitute $v=v^c$
in~\eqref{eq:conflict-kernel}. Since $v^c_c=1$, every vector in
$\ker B$ vanishes at $r$. It follows that the vectors $Bu^r$, as $r$
ranges over the $k$ original left endpoints, are linearly independent.
Indeed, a relation
\[
\sum_r\theta_r Bu^r=0
\]
puts the single vector $u=\sum_r\theta_r u^r$ in $\ker B$.
Its coordinate at each such endpoint $r$ is $u_r=\theta_r$, by
\eqref{eq:pruning-lifts}. All these coordinates vanish, so every
$\theta_r$ is zero. Furthermore,
\[
A(Bu^r)=NLu^r=0
\]
by~\eqref{eq:pruning-commute}. Thus $\dim\ker A\geq k$, establishing
the third rank condition. Equation~\eqref{eq:pruning-rank-bound} now gives
$\abs{\mathcal M}=k+\ell+t\leq\abs Z+\abs H$, as required.
\medskip\noindent
\emph{From the matching bound to a pruning.}
For completeness, we give the matching-to-cover argument in
K\H{o}nig's theorem~\cite{konig1931}. Starting at all unmatched vertices
of $\mathcal V_L$, follow edges outside $\mathcal M$ from left to
right and edges in $\mathcal M$ from right to left. Let $W_L,W_R$
be the reached vertices on the two sides. No unmatched right vertex
is reached, since an alternating path to one would augment the maximum
matching. The endpoints of a matched edge are either both reached or
both unreached: a reached right endpoint leads to its mate, and a
matched left endpoint can only have been reached through its mate.
It follows that
\[
K=(\mathcal V_L\setminus W_L)\cup W_R
\]
covers every edge. Indeed, an edge from a reached left vertex to an
unreached right vertex could be neither an unmatched edge, which would
be traversed, nor a matched edge, whose endpoints have the same
reachability. The cover contains exactly one endpoint of each matched
edge and no unmatched vertices. Hence
$\abs K=\abs{\mathcal M}\leq\abs Z+\abs H$; it also omits isolated
vertices. Applying~\eqref{eq:cover-charge} to this $K$ proves the lemma.
\end{proof}
==== END A-proof-of-Seymours-second-neighborhood-conjecture//02-pruning.tex ====
==== BEGIN A-proof-of-Seymours-second-neighborhood-conjecture//03-incompatibility.tex ====
\section{The extremal contradiction}\label{sec:incompatibility}
We use Lemma~\ref{lem:pruning} to rule out the graph supplied by
Proposition~\ref{prop:counterexample-reduction}. The proof converts the strict
subset inequalities into a strict increase of an extremal quantity associated
with two families of ordered pairs.
\begin{proposition}\label{prop:no-concavity}
There is no nonempty finite oriented graph $G$ in which every vertex has an
in-neighbor and whose one-step image operator
\[
F(U)=\{y\in V(G):x\to y\text{ for some }x\in U\}
\]
satisfies
\begin{equation}\label{eq:impossible-concavity}
\abs{U}+\abs{F^2(U)}<2\abs{F(U)}
\qquad(\varnothing\ne U\subsetneq V(G)),
\end{equation}
where $F^2=F\circ F$.
\end{proposition}
\begin{proof}
Suppose that such a graph exists, and put $X=V(G)$. For $S\subseteq X\times X$,
define the two coordinate image operators by
\[
\begin{aligned}
F_1S&=\{(i,j): (p,j)\in S\text{ and }p\to i
\text{ for some }p\in X\},\\
F_2S&=\{(i,j): (i,s)\in S\text{ and }s\to j
\text{ for some }s\in X\}.
\end{aligned}
\]
Write $F_1^2=F_1\circ F_1$, $F_2^2=F_2\circ F_2$, and
$\Delta=\{(v,v):v\in X\}$. Call $P,Q\subseteq X\times X$ \emph{compatible}
if $F_1P\cap F_2Q=\varnothing$. Equivalently, no left member $(p,j)\in P$
and right member $(i,s)\in Q$ satisfy both $p\to i$ and $s\to j$; this is
precisely the conflict relation in Lemma~\ref{lem:pruning}.
The pair $P=Q=\Delta$ is compatible: a point $(i,j)$ in both images would
require $j\to i$ and $i\to j$, contrary to orientation. Thus we may choose,
among all compatible pairs with $\Delta\subseteq P\cap Q$, one maximizing
$M+d$, where
\[
M=\abs{P}+\abs{Q},\qquad
d=\abs{X}^2-\abs{F_1P}-\abs{F_2Q}.
\]
Such a maximum exists because $X$ is finite. Compatibility makes $d$ the
number of points outside $F_1P\cup F_2Q$. Including these uncovered points
in the objective lets the points left uncovered by pruning offset the
corresponding part of the deletion cost.
Every column $P_j=\{p:(p,j)\in P\}$ is nonempty, since $j\in P_j$.
It is also proper. Indeed, positive indegrees give $F(X)=X$, so $P_j=X$
would imply $X\times\{j\}\subseteq F_1P$. Choose an in-neighbor $w$ of
$j$. Then $(w,j)\in F_2\Delta\subseteq F_2Q$, contradicting compatibility.
Likewise every row $Q_i=\{s:(i,s)\in Q\}$ contains $i$. If $Q_i=X$,
then $\{i\}\times X\subseteq F_2Q$; choosing $w\to i$ gives
$(i,w)\in F_1\Delta\subseteq F_1P$, again a contradiction.
We can therefore sum~\eqref{eq:impossible-concavity} over the columns of $P$
and over the rows of $Q$ to obtain
\begin{equation}\label{eq:strict-fiber-sums}
\abs{P}+\abs{F_1^2P}<2\abs{F_1P},\qquad
\abs{Q}+\abs{F_2^2Q}<2\abs{F_2Q}.
\end{equation}
Define new left and right families by taking complements in $X\times X$:
\[
\mathcal R=(X\times X)\setminus F_2^2Q,
\qquad
\mathcal C=(X\times X)\setminus F_1^2P.
\]
The two strict inequalities in~\eqref{eq:strict-fiber-sums} give
\begin{equation}\label{eq:complement-gain}
\begin{aligned}
\abs{\mathcal R}+\abs{\mathcal C}
&=2\abs{X}^2-\abs{F_2^2Q}-\abs{F_1^2P}\\
&>2\abs{X}^2+M-2\bigl(\abs{F_1P}+\abs{F_2Q}\bigr)
=M+2d.
\end{aligned}
\end{equation}
These families need not be compatible. We will apply the pruning lemma,
first verifying that the diagonal survives and then bounding the cost.
Both families contain $\Delta$. If $(v,v)\in F_2^2Q$, there is an $s\to v$
with $(v,s)\in F_2Q$. But $(s,s)\in P$ gives $(v,s)\in F_1P$, a
contradiction. If $(v,v)\in F_1^2P$, there is a $p\to v$ with
$(p,v)\in F_1P$. Now $(p,p)\in Q$ gives $(p,v)\in F_2Q$, the same
contradiction.
Moreover, each diagonal member is conflict-free in the new families.
A conflict between the left member $(v,v)$ and a right member
$(i,s)\in\mathcal C$ would give the path $s\to v\to i$.
Starting at $(s,s)\in P$ and expanding its first coordinate twice would
then put $(i,s)$ in $F_1^2P$, contrary to its membership in $\mathcal C$.
A conflict between a left member $(p,j)\in\mathcal R$ and the right member
$(v,v)$ would give $p\to v\to j$. Expanding the second coordinate of
$(p,p)\in Q$ twice would put $(p,j)$ in $F_2^2Q$, again a contradiction.
The preservation clause of Lemma~\ref{lem:pruning} thus applies to every
diagonal member on both sides.
Let $H,Z\subseteq X\times X$ be the sets associated with
$\mathcal R,\mathcal C$ in that lemma. Thus each conflict
\[
(p,j)\in\mathcal R,\quad (i,s)\in\mathcal C,\quad
p\to i,\quad s\to j
\]
contributes $(p,s)$ to $H$ and $(i,j)$ to $Z$.
We claim that
\begin{equation}\label{eq:old-uncovered-bound}
H\subseteq (X\times X)\setminus(F_1P\cup F_2Q),
\qquad\text{and hence}\qquad \abs{H}\le d.
\end{equation}
To see this, fix such a conflict. If $(p,s)\in F_1P$, choose
$(u,s)\in P$ with $u\to p$. The path $u\to p\to i$ then puts
$(i,s)$ in $F_1^2P$, contrary to $(i,s)\in\mathcal C$.
If $(p,s)\in F_2Q$, choose $(p,t)\in Q$ with $t\to s$.
The path $t\to s\to j$ puts $(p,j)$ in $F_2^2Q$, contrary to
$(p,j)\in\mathcal R$. This proves~\eqref{eq:old-uncovered-bound}.
Apply Lemma~\ref{lem:pruning} to obtain conflict-free families
$P'\subseteq\mathcal R$ and $Q'\subseteq\mathcal C$.
They still contain $\Delta$, and their lack of conflicts means
$F_1P'\cap F_2Q'=\varnothing$. Set
\[
d'=\abs{X}^2-\abs{F_1P'}-\abs{F_2Q'}.
\]
A point is covered by a kept left member exactly when it belongs to
$F_1P'$, and by a kept right member exactly when it belongs to $F_2Q'$.
Consequently at most $d'$ points of $Z$ are uncovered after pruning.
By Lemma~\ref{lem:pruning} and~\eqref{eq:old-uncovered-bound}, at most $d+d'$ members
were deleted, counting the two sides separately. Using
\eqref{eq:complement-gain}, we conclude that
\[
\begin{aligned}
\abs{P'}+\abs{Q'}+d'
&\ge \abs{\mathcal R}+\abs{\mathcal C}-(d+d')+d'\\
&>M+2d-(d+d')+d'=M+d.
\end{aligned}
\]
This contradicts the choice of $P,Q$ and proves the proposition.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{thm:main}]
If the theorem were false, Proposition~\ref{prop:counterexample-reduction}
would produce a nonempty finite oriented graph with positive indegrees
satisfying~\eqref{eq:impossible-concavity} for every nonempty proper vertex
set. Proposition~\ref{prop:no-concavity} rules out such a graph.
\end{proof}
==== END A-proof-of-Seymours-second-neighborhood-conjecture//03-incompatibility.tex ====
==== BEGIN A-proof-of-Seymours-second-neighborhood-conjecture//04-weighted-consequences.tex ====
\section{Weighted consequences}\label{sec:weighted-consequences}
The following corollary applies Theorem~\ref{thm:main} through Seacrest's
established equivalences of the corresponding assertions over all nonempty
finite oriented graphs~\cite{Seacrest2015}. The equivalences themselves are
not new here.
\begin{corollary}[Weighted second-neighborhood forms]\label{cor:weighted-forms}
Let \(D\) be a nonempty finite oriented graph, and write \(A(D)\) for its
arc set. For a vertex weighting \(\eta:V(D)\to[0,\infty)\), write
\(\eta(S)=\sum_{x\in S}\eta(x)\). Then the following hold.
\begin{enumerate}[label=\textup{(\roman*)}]
\item For every vertex weighting \(\eta:V(D)\to[0,\infty)\), there is a
vertex \(v\in V(D)\) such that
\[
\eta(N_1^+(v))\leq\eta(N_2^+(v)).
\]
\item There is a vertex weighting \(\eta:V(D)\to[0,\infty)\) with
\(\sum_{x\in V(D)}\eta(x)=1\) such that
\[
\eta(N_1^+(v))\leq\eta(N_2^+(v))\qquad\text{for every }v\in V(D).
\]
The entries of this weighting need not all be positive.
\item For every arc weighting \(w:A(D)\to[0,\infty)\), extend the notation
by setting \(w(vs)=0\) when \(vs\notin A(D)\). For \(v,s\in V(D)\), put
\[
\beta_v^w(s)=\max\Bigl(\{0\}\cup
\{w(us)-w(vs):u\in V(D),\ v\to u\to s\}\Bigr).
\]
Then there is a vertex \(v\in V(D)\) such that
\[
\sum_{s\in V(D)}\beta_v^w(s)
\geq \sum_{u\in N_1^+(v)}w(vu).
\]
The maximum is zero if there is no indicated two-step path. Such paths
are determined by the arcs of \(D\), so an arc of weight zero is still
present and is not treated as a missing arc.
\end{enumerate}
\end{corollary}
\begin{proof}
Seacrest's Proposition~2 proves that his arc-weighted Conjecture~4 is
equivalent to the unweighted conjecture, so Theorem~\ref{thm:main} gives
\textup{(iii)}.
To obtain \textup{(i)}, set $w(us)=\eta(s)$ on every arc. For each $v,s$,
\[
\beta_v^w(s)=
\begin{cases}
\eta(s),&s\in N_2^+(v),\\
0,&s\notin N_2^+(v).
\end{cases}
\]
Indeed, when $v\to s$, every eligible difference $w(us)-w(vs)$ is zero.
At an exact second out-neighbor, $w(vs)=0$ and the maximum is $\eta(s)$;
no other endpoint contributes. Thus the two sides of \textup{(iii)}
become $\eta(N_2^+(v))$ and $\eta(N_1^+(v))$. This is the
specialization noted immediately after Seacrest's Proposition~2.
For \textup{(ii)}, let $M_D$ have entry $1$ at $(v,s)$ when
$s\in N_2^+(v)$, entry $-1$ when $s\in N_1^+(v)$, and zero otherwise.
Reversing all arcs transposes this matrix:
$M_{\overleftarrow D}=M_D^{\mathsf T}$. Seacrest's Theorem~1 applies
Farkas' lemma to give either a nonzero $\eta\ge0$ with $M_D\eta\ge0$,
or a $\xi\ge0$ with $M_D^{\mathsf T}\xi<0$ at every coordinate.
The latter contradicts \textup{(i)} on $\overleftarrow D$.
Normalize the former weighting to total weight one, proving \textup{(ii)}.
\end{proof}
==== END A-proof-of-Seymours-second-neighborhood-conjecture//04-weighted-consequences.tex ====
==== BEGIN A-proof-of-Seymours-second-neighborhood-conjecture//05-directed-cycle-consequences.tex ====
\section{Directed-cycle consequences}\label{sec:directed-cycle-consequences}
In an oriented graph with no directed triangle, every exact second
out-neighbor is a non-neighbor. Combining this observation with
Theorem~\ref{thm:main} gives degree and order bounds.
The first assertion below is the oriented-graph form of Thomass\'e's
non-neighbor statement recorded by
Sullivan~\cite[Conjecture~6.12]{Sullivan2006}.
The consequence using both minimum indegree and minimum outdegree is also
noted in \cite[Section~3]{Sullivan2006}. The regular case gives the
girth-four lower bound in the Behzad--Chartrand--Wall minimum-order
conjecture~\cite{BehzadChartrandWall1970}, also recorded by
Sullivan~\cite[Section~4]{Sullivan2006}.
\begin{corollary}[Non-neighbors and directed cycles]\label{cor:directed-cycle-consequences}
Let \(D\) be a nonempty finite oriented graph of order \(n\). For
\(v\in V(D)\), write
\[
N_1^-(v)=\{u:u\to v\},\qquad
d^\pm(v)=\abs{N_1^\pm(v)},\qquad
\delta^\pm(D)=\min_{x\in V(D)}d^\pm(x).
\]
Define the non-neighbors of \(v\), excluding \(v\) itself, by
\[
Z(v)=V(D)\setminus
\bigl(\{v\}\cup N_1^+(v)\cup N_1^-(v)\bigr).
\]
Then the following hold.
\begin{enumerate}[label=\textup{(\roman*)}]
\item If \(D\) has no directed \(3\)-cycle, then some vertex \(v\) satisfies
\[
d^+(v)\leq\abs{Z(v)},\qquad
n-1\geq 2d^+(v)+d^-(v).
\]
\item If \(\delta^+(D)\geq n/3\) and \(\delta^-(D)\geq n/3\), then \(D\)
contains a directed \(3\)-cycle.
\item If \(r\geq1\) is an integer, \(d^+(v)=d^-(v)=r\) for every vertex,
and \(D\) has directed girth exactly four, then \(n\geq3r+1\).
\end{enumerate}
Here directed girth is the length of a shortest directed cycle.
\end{corollary}
\begin{proof}
Suppose that \(D\) has no directed \(3\)-cycle. If \(w\in N_2^+(v)\),
choose a path \(v\to u\to w\). The exact-distance definition excludes
\(w=v\) and \(w\in N_1^+(v)\). If \(w\in N_1^-(v)\), the arc \(w\to v\)
would close a directed \(3\)-cycle. Thus
\(N_2^+(v)\subseteq Z(v)\) for every \(v\). Theorem~\ref{thm:main}
now gives a vertex with
\[
d^+(v)\leq\abs{N_2^+(v)}\leq\abs{Z(v)}.
\]
Since \(D\) is oriented, its first in- and out-neighborhoods are disjoint,
and their cardinalities are the corresponding degrees. Hence
\[
n-1=d^+(v)+d^-(v)+\abs{Z(v)}
\geq 2d^+(v)+d^-(v),
\]
proving \textup{(i)}.
Under the hypotheses of \textup{(ii)}, absence of a directed \(3\)-cycle
would therefore give
\[
n-1\geq2\delta^+(D)+\delta^-(D)\geq n,
\]
a contradiction. The integer degree thresholds are
\(\delta^\pm(D)\geq\lceil n/3\rceil\), so this includes the endpoint
when \(3\) divides \(n\). Finally, directed girth four excludes directed
\(3\)-cycles; in the regular case the count in \textup{(i)} becomes
\(n-1\geq3r\), proving \textup{(iii)}.
\end{proof}
==== END A-proof-of-Seymours-second-neighborhood-conjecture//05-directed-cycle-consequences.tex ====
==== BEGIN A-proof-of-Seymours-second-neighborhood-conjecture//main.tex ====
\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\pdfglyphtounicode{parenleftbig}{0028}
\pdfglyphtounicode{parenrightbig}{0029}
\pdfglyphtounicode{parenleftBig}{0028}
\pdfglyphtounicode{parenrightBig}{0029}
\pdfgentounicode=1
\usepackage[margin=1.05in]{geometry}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{microtype}
\usepackage{enumitem}
\usepackage{tikz}
\usetikzlibrary{arrows.meta,positioning,calc}
\usepackage[hidelinks]{hyperref}
\hypersetup{pdftitle={A proof of Seymour's second-neighborhood conjecture},
pdfauthor={OpenAI}, pdfsubject={Oriented graphs and finite relations}}
\pdftrailerid{}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\abs}[1]{\lvert #1\rvert}
\DeclareMathOperator{\rank}{rank}
\DeclareMathOperator{\im}{im}
\newcommand{\R}{\mathbb R}
\title{A proof of Seymour's second-neighborhood conjecture}
\author{OpenAI}
\date{September 23, 2026}
\begin{document}
\maketitle
\begin{abstract}
We prove that every nonempty finite oriented graph has a vertex with at least
as many vertices at directed distance two as at directed distance one.
This resolves Seymour's second neighborhood conjecture positively.
\end{abstract}
\input{00-introduction}
\input{01-reduction}
\input{02-pruning}
\input{03-incompatibility}
\input{04-weighted-consequences}
\input{05-directed-cycle-consequences}
\bibliographystyle{plain}
\bibliography{references}
\end{document}
==== END A-proof-of-Seymours-second-neighborhood-conjecture//main.tex ====
==== BEGIN A-proof-of-Seymours-second-neighborhood-conjecture//pruning.tex ====
\begin{tikzpicture}[
every node/.style={font=\small},
original/.style={circle,draw,fill=black!7,minimum size=8mm,inner sep=1pt},
copy/.style={rectangle,draw,minimum size=8mm,inner sep=3pt},
edge label/.style={font=\footnotesize,above=4pt},
family label/.style={font=\footnotesize,below=6pt}
]
\node[copy] (zl) at (0,0) {$z_L$};
\node[original] (c) at (3,0) {$c$};
\node[original] (r) at (6,0) {$r$};
\node[copy] (zr) at (9,0) {$z_R$};
\draw[dashed] (zl) -- node[edge label] {covers $z$} (c);
\draw (c) -- node[edge label] {conflict} (r);
\draw[dashed] (r) -- node[edge label] {covers $z$} (zr);
\node[family label] at (zl.south) {$Z_L$};
\node[family label] at (c.south) {$\mathcal C:\ (i,s)$};
\node[family label] at (r.south) {$\mathcal R:\ (p,j)$};
\node[family label] at (zr.south) {$Z_R$};
\end{tikzpicture}
==== END A-proof-of-Seymours-second-neighborhood-conjecture//pruning.tex ====
==== BEGIN A-proof-of-Seymours-second-neighborhood-conjecture//references.bib ====
@article{Fisher1996,
author = {Fisher, David C.},
title = {Squaring a tournament: A proof of {Dean}'s conjecture},
journal = {Journal of Graph Theory},
volume = {23},
number = {1},
year = {1996},
pages = {43--48},
doi = {10.1002/(SICI)1097-0118(199609)23:1<43::AID-JGT4>3.0.CO;2-K},
url = {https://doi.org/10.1002/(SICI)1097-0118(199609)23:1<43::AID-JGT4>3.0.CO;2-K},
note = {\href{https://doi.org/10.1002/(SICI)1097-0118(199609)23:1<43::AID-JGT4>3.0.CO;2-K}{doi}}
}
@article{HavetThomasse2000,
author = {Havet, Fr{\'e}d{\'e}ric and Thomass{\'e}, St{\'e}phan},
title = {Median orders of tournaments: A tool for the second neighborhood problem and {Sumner}'s conjecture},
journal = {Journal of Graph Theory},
volume = {35},
number = {4},
year = {2000},
pages = {244--256},
doi = {10.1002/1097-0118(200012)35:4<244::AID-JGT2>3.0.CO;2-H},
url = {https://doi.org/10.1002/1097-0118(200012)35:4<244::AID-JGT2>3.0.CO;2-H},
note = {\href{https://doi.org/10.1002/1097-0118(200012)35:4<244::AID-JGT2>3.0.CO;2-H}{doi}}
}
@misc{Seacrest2019,
author = {Seacrest, Tyler},
title = {{Seymour}'s Second Neighborhood Conjecture for Subsets of Vertices},
year = {2019},
eprint = {1808.06293v3},
archivePrefix = {arXiv},
primaryClass = {math.CO},
doi = {10.48550/arXiv.1808.06293},
url = {https://arxiv.org/abs/1808.06293v3},
note = {\href{https://arxiv.org/abs/1808.06293v3}{arXiv:1808.06293v3} [math.CO], revised 12 April 2019}
}
@article{Seacrest2015,
author = {Seacrest, Tyler},
title = {The Arc-Weighted Version of the Second Neighborhood Conjecture},
journal = {Journal of Graph Theory},
volume = {78},
number = {3},
year = {2015},
pages = {219--228},
doi = {10.1002/jgt.21800},
url = {https://doi.org/10.1002/jgt.21800},
note = {Preprint (numbering used here): \href{https://arxiv.org/abs/1212.1883v1}{arXiv:1212.1883v1}}
}
@article{konig1931,
author = {K{\H{o}}nig, D{\'e}nes},
title = {Graphok {\'e}s matrixok},
journal = {Matematikai {\'e}s Fizikai Lapok},
volume = {38},
year = {1931},
pages = {116--119},
url = {https://real-j.mtak.hu/7307/},
note = {In Hungarian}
}
@article{DeanLatka1995,
author = {Dean, Nathaniel and Latka, Brenda J.},
title = {Squaring the tournament---an open problem},
journal = {Congressus Numerantium},
volume = {109}, year = {1995}, pages = {73--80}
}
@article{FidlerYuster2007,
author = {Fidler, Dror and Yuster, Raphael},
title = {Remarks on the second neighborhood problem},
journal = {Journal of Graph Theory},
volume = {55}, number = {3}, year = {2007}, pages = {208--220},
doi = {10.1002/jgt.20229},
url = {https://doi.org/10.1002/jgt.20229}
}
@article{Ghazal2012,
author = {Ghazal, Salman},
title = {{Seymour}'s second neighborhood conjecture for tournaments missing a generalized star},
journal = {Journal of Graph Theory},
volume = {71}, number = {1}, year = {2012}, pages = {89--94},
doi = {10.1002/jgt.20634},
url = {https://doi.org/10.1002/jgt.20634}
}
@article{DaraFrancisJacobNarayanan2022,
author = {Dara, Suresh and Francis, Mathew C. and Jacob, Dalu and Narayanan, N.},
title = {Extending some results on the second neighborhood conjecture},
journal = {Discrete Applied Mathematics},
volume = {311}, year = {2022}, pages = {1--17},
doi = {10.1016/j.dam.2021.12.034},
url = {https://doi.org/10.1016/j.dam.2021.12.034}
}
@article{DaamouchAlMninyGhazal2025,
author = {Daamouch, Moussa and Al-Mniny, Darine and Ghazal, Salman},
title = {About the second neighborhood conjecture for tournaments missing two stars or disjoint paths},
journal = {Contributions to Discrete Mathematics},
volume = {20}, number = {2}, year = {2025}, pages = {363--383},
doi = {10.55016/ojs/cdm.v20i2.77499},
url = {https://cdm.ucalgary.ca/article/download/77499/58529/271837}
}
@article{KanekoLocke2001,
author = {Kaneko, Yoshihiro and Locke, Stephen C.},
title = {The minimum degree approach for {Paul Seymour}'s distance 2 conjecture},
journal = {Congressus Numerantium},
volume = {148}, year = {2001}, pages = {201--206}
}
@misc{SadhukhanSandeepSen2026,
author = {Sadhukhan, Arpan and Sandeep, R. B. and Sen, Sagnik},
title = {A proof of {Seymour}'s second neighborhood conjecture for oriented graphs with minimum out-degree equal to 7},
year = {2026}, eprint = {2606.30588v1},
archivePrefix = {arXiv}, primaryClass = {math.CO},
url = {https://arxiv.org/abs/2606.30588v1},
note = {arXiv:2606.30588v1, June 29, 2026}
}
@article{ChenShenYuster2003,
author = {Chen, Guantao and Shen, Jian and Yuster, Raphael},
title = {Second neighborhood via first neighborhood in digraphs},
journal = {Annals of Combinatorics},
volume = {7}, number = {1}, year = {2003}, pages = {15--20},
doi = {10.1007/s000260300001},
url = {https://doi.org/10.1007/s000260300001}
}
@misc{HuangPeng2024,
author = {Huang, Hao and Peng, Fei},
title = {An improved bound on {Seymour}'s second neighborhood conjecture},
year = {2024}, eprint = {2412.20234v1},
archivePrefix = {arXiv}, primaryClass = {math.CO},
url = {https://arxiv.org/abs/2412.20234v1},
note = {arXiv:2412.20234v1, December 28, 2024}
}
@article{BotlerMouraNaia2023,
author = {Botler, F{\'a}bio and Moura, Phablo F. S. and Naia, T{\'a}ssio},
title = {{Seymour}'s second neighborhood conjecture for orientations of (pseudo)random graphs},
journal = {Discrete Mathematics},
volume = {346}, number = {12}, year = {2023}, pages = {113583},
doi = {10.1016/j.disc.2023.113583},
url = {https://doi.org/10.1016/j.disc.2023.113583}
}
@article{EspunyDiazEtAl2025,
author = {Espuny D{\'i}az, Alberto and Gir{\~a}o, Ant{\'o}nio and Granet, Bertille and Kronenberg, Gal},
title = {{Seymour}'s second neighbourhood conjecture: random graphs and reductions},
journal = {Random Structures \& Algorithms},
volume = {66}, number = {1}, year = {2025}, pages = {e21251},
doi = {10.1002/rsa.21251},
url = {https://doi.org/10.1002/rsa.21251}
}
@misc{Brukhman2026,
author = {Brukhman, Jake},
title = {A dense-case theorem for {Seymour}'s second neighborhood conjecture},
year = {2026}, eprint = {2608.11530v1},
archivePrefix = {arXiv}, primaryClass = {math.CO},
url = {https://arxiv.org/abs/2608.11530v1},
note = {arXiv:2608.11530v1, August 12, 2026}
}
@article{BrantnerBrockmanKaySnively2009,
author = {Brantner, James and Brockman, Greg and Kay, Bill and Snively, Emma},
title = {Contributions to {Seymour}'s second neighborhood conjecture},
journal = {Involve},
volume = {2}, number = {4}, year = {2009}, pages = {387--395},
url = {https://msp.org/involve/2009/2-4/involve-v2-n4-p02-s.pdf}
}
@article{Edmonds1967,
author = {Edmonds, Jack},
title = {Systems of distinct representatives and linear algebra},
journal = {Journal of Research of the National Bureau of Standards, Section B},
volume = {71B}, number = {4}, year = {1967}, pages = {241--245},
doi = {10.6028/jres.071B.033},
url = {https://doi.org/10.6028/jres.071B.033}
}
@misc{Sullivan2006,
author = {Sullivan, Blair D.},
title = {A Summary of Results and Problems Related to the {Caccetta--H{\"a}ggkvist} Conjecture},
year = {2006},
howpublished = {American Institute of Mathematics},
url = {https://aimath.org/WWN/caccetta/caccetta.pdf},
note = {AIM workshop report dated April 14, 2006;
\href{https://aimath.org/WWN/caccetta/caccetta.pdf}{report};
Section~3 and Conjecture~6.12}
}
@article{BehzadChartrandWall1970,
author = {Behzad, Mehdi and Chartrand, Gary and Wall, Curtiss E.},
title = {On minimal regular digraphs with given girth},
journal = {Fundamenta Mathematicae},
volume = {69},
number = {3},
year = {1970},
pages = {227--231},
doi = {10.4064/fm-69-3-227-231},
url = {https://doi.org/10.4064/fm-69-3-227-231},
note = {\href{https://doi.org/10.4064/fm-69-3-227-231}{doi}}
}
==== END A-proof-of-Seymours-second-neighborhood-conjecture//references.bib ====