The Setting
A digraph on a finite vertex set , with for an arc, is an oriented graph when it has no loop and no pair of opposite arcs and .✦
The first neighborhood of a vertex of is the set of its out-neighbors✦, and the second neighborhood is the set of vertices at directed distance exactly two from : (1)✦ A vertex is good when , and Seymour’s second-neighborhood conjecture asserts that every oriented graph has a good vertex. A counterexample on is a digraph on with no good vertex✦, and an oriented counterexample is a counterexample that is an oriented graph.
The lemma looks at oriented counterexamples that are as small as possible, first in their number of vertices and then in their number of arcs. The question is what this minimality forces on a set of vertices and on the vertices it reaches along one arc and along two.
Images and Minimality
The image of a set of vertices of is the set of vertices that receive an arc from some vertex of , , and .✦ The set is not removed, so may meet .
Write for the standard set of vertices. A digraph on has minimum order when (2)✦
The arc set of a digraph on is the set of pairs of vertices with .✦ A digraph on has the fewest arcs on when (3)✦
The Claim
Theorem 1. Let be an oriented counterexample on a finite vertex set .
If has minimum order, then has nonempty boundary: (4)✦
If has nonempty boundary, then has positive indegree: (5)✦
If has nonempty boundary and has the fewest arcs on , then has the subset deficit: (6)✦
If is nonempty, then for some there is an oriented counterexample on such that (7)✦
In the paper, the result reads: if is a finite nonempty oriented graph with for every vertex , chosen with minimum order and, subject to that, with the minimum number of arcs among all graphs with this property, then is strongly connected, every vertex has positive indegree, and for every with .
What Is Checked
The lemma is stated over oriented counterexamples on a finite vertex set, with their first and second neighborhoods (1), the image and the arc set , and over the conditions of minimum order (2), fewest arcs (3), nonempty boundary (4), positive indegree (5) and the subset deficit (6).