OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction

Theorem 1.1: Seymour's second-neighborhood conjecture: some vertex has at least as many vertices at directed distance two as out-neighbors

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 an oriented graph DD on a finite set VV and a vertex vv of DD. From vv some vertices are reached along one arc, and others along two arcs but not along one. Seymour’s second-neighborhood conjecture asks whether every such graph with at least one vertex has a vertex vv for which the second kind are at least as many as the first.

Oriented Graphs and Out-neighborhoods

A digraph DD on a finite set VV is a set of ordered pairs of elements of VV, its arcs; we write u→wu \to w when (u,w)(u, w) is an arc of DD.

An oriented graph on VV is a digraph on VV with no loop v→vv \to v and no pair of opposite arcs u→wu \to w and w→uw \to u.✦

The first out-neighborhood N1+(v)N_1^+(v) of a vertex vv of DD is the set of the vertices that vv sends an arc to: N1+(v)={u∈V:v→u}.N_1^+(v) = \{u \in V : v \to u\}.(1)✦

The second out-neighborhood N2+(v)N_2^+(v) of a vertex vv of DD is the set of the vertices at directed distance exactly two from vv: N2+(v)={w∈V:w≠v,v↛w, and v→u→w for some u∈V}.N_2^+(v) = \{w \in V : w \neq v,\ v \not\to w, \text{ and } v \to u \to w \text{ for some } u \in V\}.(2)✦

The Claim

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

What Is Checked

The library states the claim over every oriented graph on a nonempty finite set, with the out-neighborhoods (1) and (2) and the good vertices of (3).