The Setting
Take an oriented graph on a finite set and a vertex of . From 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 for which the second kind are at least as many as the first.
Oriented Graphs and Out-neighborhoods
A digraph on a finite set is a set of ordered pairs of elements of , its arcs; we write when is an arc of .
An oriented graph on is a digraph on with no loop and no pair of opposite arcs and .✦
The first out-neighborhood of a vertex of is the set of the vertices that sends an arc to: (1)✦
The second out-neighborhood of a vertex of is the set of the vertices at directed distance exactly two from : (2)✦
The Claim
Theorem 1 (Seymour’s second-neighborhood conjecture). Let be an oriented graph on a nonempty finite set . Then has a good vertex: a vertex with (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).