OctoInformBeta

OpenAI preprint, September 2026 · §4. The extremal contradiction

Proof of Theorem 1.1: Seymour's second-neighborhood conjecture, with the reduction of a counterexample to an oriented graph of strict growth and the pruning theorem for pairs

Every nonempty finite oriented graph has a good vertex.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Take a finite oriented graph, a tournament say, and a vertex vv of it. Some vertices are out-neighbors of vv; others are reached from vv by a directed path of length two and by no arc. Must some vertex have at least as many vertices of the second kind as of the first? Seymour’s second-neighborhood conjecture says that it must.

The library states the conjecture for every oriented graph on a nonempty finite vertex set, beside two statements: a reduction of a counterexample to an oriented graph of a special kind on a grid of vertices, and a pruning theorem on deleting pairs from two families of pairs of points under a relation.

Neighborhoods and Growth

A digraph DD on a finite vertex set VV, written with arrows u→wu \to w for its arcs, is oriented when it has no loop v→vv \to v and no pair of opposite arcs u→wu \to w and w→uw \to u.✦ The first neighborhood N1+(v)N_1^+(v) of a vertex vv of DD is the set of its out-neighbors✦, and its second neighborhood N2+(v)N_2^+(v) is the set of the vertices at directed distance exactly two from vv: N1+(v)={u:v→u},N2+(v)={w:w≠v,v↛w,v→u→w for some u}.N_1^+(v) = \{u : v \to u\}, \qquad N_2^+(v) = \{w : w \ne v,\ v \not\to w,\ v \to u \to w \text{ for some } u\}.(1)✦

The image F(S)F(S) of a set SS of vertices of DD is the set of the vertices, in SS or not, that receive an arc from a vertex of SS, and F2(S)=F(F(S))F^2(S) = F(F(S)): F(S)={y:x→y for some x∈S}.F(S) = \{y : x \to y \text{ for some } x \in S\}.(2)✦ A digraph DD on VV has positive indegree when every vertex vv has an in-neighbor, a vertex uu with u→vu \to v✦, and strict growth when every nonempty proper subset S⊊VS \subsetneq V satisfies |S|+|F2(S)|<2|F(S)|.|S| + |F^2(S)| < 2\,|F(S)|.(3)✦

Conflicting Pairs

Let →\to be a relation on a set XX, and call the elements of X×XX \times X pairs. A pair (p,j)(p, j) conflicts with a pair (i,s)(i, s) when p→ip \to i and s→js \to j.✦ Two finite families ℛ\mathcal R and 𝒞\mathcal C of pairs are conflict-free when no pair of ℛ\mathcal R conflicts with a pair of 𝒞\mathcal C.✦ For finite families ℛ\mathcal R and 𝒞\mathcal C, the set ZZ collects the points (i,j)(i, j)✦ and the set HH the points (p,s)(p, s) of the conflicts between ℛ\mathcal R and 𝒞\mathcal C: Z={(i,j):(p,j)∈ℛ conflicts with (i,s)∈𝒞 for some p,s},H={(p,s):(p,j)∈ℛ conflicts with (i,s)∈𝒞 for some i,j}.\begin{aligned} Z &= \{(i, j) : (p, j) \in \mathcal R \text{ conflicts with } (i, s) \in \mathcal C \text{ for some } p, s\},\\ H &= \{(p, s) : (p, j) \in \mathcal R \text{ conflicts with } (i, s) \in \mathcal C \text{ for some } i, j\}. \end{aligned}(4)✦

The left image F1SF_1 S and the right image F2SF_2 S of a finite family SS of pairs advance the first, respectively the second, coordinate along an arc: F1S={(i,j):p→i for some (p,j)∈S},F2S={(i,j):s→j for some (i,s)∈S}.F_1 S = \{(i, j) : p \to i \text{ for some } (p, j) \in S\}, \qquad F_2 S = \{(i, j) : s \to j \text{ for some } (i, s) \in S\}.(5) A pair is covered by finite families ℛ\mathcal R and 𝒞\mathcal C when it lies in F1ℛ∪F2𝒞F_1 \mathcal R \cup F_2 \mathcal C.✦ For two further finite families ℛ′\mathcal R' and 𝒞′\mathcal C', the uncovered part UU of ZZ is the set of the points of ZZ that are not covered by ℛ′\mathcal R' and 𝒞′\mathcal C'.✦

The Claim

Theorem 1 (Seymour’s second-neighborhood conjecture). Let DD be an oriented graph on a nonempty finite vertex set VV. Then DD has a good vertex, a vertex vv with |N1+(v)|≤|N2+(v)|.|N_1^+(v)| \le |N_2^+(v)|.(6)✦

Theorem 2 (Counterexample reduction). Let DD be an oriented graph on a nonempty finite vertex set VV that is a counterexample to Seymour’s conjecture, one with no good vertex. Then there are a positive integer nn and an oriented graph GG with positive indegree and strict growth on the vertex set {0,…,n−1}×{0,…,n}.\{0, \dots, n-1\} \times \{0, \dots, n\}.(7)✦

Theorem 3 (Pruning theorem). Let →\to be a relation on a set XX. Then →\to satisfies the pruning statement: any two finite families ℛ\mathcal R and 𝒞\mathcal C of pairs admit a pruning result, conflict-free subfamilies ℛ′⊆ℛ\mathcal R' \subseteq \mathcal R and 𝒞′⊆𝒞\mathcal C' \subseteq \mathcal C that keep every pair of ℛ\mathcal R or 𝒞\mathcal C in no conflict between ℛ\mathcal R and 𝒞\mathcal C and satisfy |ℛ\ℛ′|+|𝒞\𝒞′|≤|H|+|U|,|\mathcal R \setminus \mathcal R'| + |\mathcal C \setminus \mathcal C'| \le |H| + |U|,(8)✦ where UU is the uncovered part of ZZ for ℛ′\mathcal R' and 𝒞′\mathcal C'.

What Is Checked

The three theorems are stated over oriented graphs on a nonempty finite vertex set, with the first and second neighborhoods of their vertices and good vertices; over counterexamples to Seymour’s conjecture, positive indegree, the image of a vertex set and strict growth; and over a relation on a set, with conflicting pairs, conflict-free families, the sets ZZ and HH, the left and right images, covered pairs, the uncovered part of ZZ, pruning results and the pruning statement.