OpenAI preprint, September 2026 · §2. From a counterexample to a strict subset inequality
Counterexamples, minimality and the subset conditions:Order and arc minimality, positive indegree, and three conditions on the images of a nonempty proper vertex set
A counterexample is a digraph with no 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 and a vertex of it, and compare the number of out-neighbors of with the number of vertices at directed distance two from . Seymour’s second neighborhood conjecture says that every oriented graph has a vertex for which the second number is at least the first. These notes define its counterexamples and two senses in which a counterexample is smallest, together with four conditions on a digraph: one on the in-neighbors of its vertices, three on how a set of vertices grows when one follows the arcs out of it once and then twice.
Neighborhoods and Images
A digraph on a finite vertex set is given by its arcs between vertices of , an arc from to being written .A digraph on is oriented when it has no loop and no pair of opposite arcs and .✦
The first and second out-neighborhoods of a vertex of are the sets (1)A vertex of is good when .✦The second neighborhood conjecture for a digraph on is the assertion that some vertex of is good.✦
The image of a set of vertices of is the set of vertices that receive an arc from some vertex of , and is the image of :(2)✦ The image may meet . A set of vertices of is proper when .
The Claim
Definition 1. A digraph on a finite vertex set is a counterexample to the second neighborhood conjecture when (3)✦A digraph on is order-minimal when (4)✦The arc set of a digraph on is (5)✦ and is arc-minimal when (6)✦A digraph on has positive indegree when (7)✦ A digraph on has nonempty out-boundaries when (8)✦ A digraph on satisfies the subset deficit when (9)✦ A digraph on has strict growth when (10)✦
What Is Checked
The conditions (3) to (10) are stated for a digraph on a finite vertex set , over its out-neighborhoods (1), its good vertices and the second neighborhood conjecture for , the images(2) of its proper sets of vertices, and, in the two minimality conditions, the oriented counterexamples on vertices and on .