The Setting
A digraph on a finite vertex set , with an arc written , is oriented when it has no loop and no pair of opposite arcs and .✦ The first out-neighborhood of a vertex of is the set of its out-neighbors✦, and its second out-neighborhood is the set of vertices at directed distance exactly two from , each counted once: (1)✦
A vertex is good when , and Seymour’s second-neighborhood conjecture asserts that every oriented graph on a nonempty finite vertex set has a good vertex. A counterexample to the conjecture is an oriented graph on in which no vertex is good: (2)✦
Images of Vertex Sets
The claim below carries the failure (2) from single vertices to sets of vertices, measured by their images. The image of a set of vertices of a digraph on is the set of vertices that receive an arc from some vertex of , and the second image of is : (3)✦ The image may meet , and is written for the image in a digraph when more than one digraph is in play.
A set of vertices is proper when . A digraph on has positive indegree when every vertex has an in-neighbor, a vertex with .✦
The Claim
Theorem 1. Let be a counterexample to Seymour’s second-neighborhood conjecture, an oriented graph on a nonempty finite vertex set satisfying (2). For a positive integer write . Then there are a positive integer and an oriented graph on the vertex set that has positive indegree and strict growth: every nonempty proper set of vertices of satisfies (4)✦
In the paper, the result reads: if the paper’s Theorem 1.1 has a counterexample, then there is a finite nonempty oriented graph in which every vertex has positive indegree and for every nonempty proper vertex set of .
What Is Checked
The claim is stated over oriented graphs on finite vertex sets, the out-neighborhoods (1) and the counterexample condition (2) built from them, the image (3), positive indegree and strict growth (4).