The Setting
Take a digraph on a finite vertex set : a set of arcs between vertices of , in which a loop and a pair of opposite arcs may occur. These notes give the operator that takes one step, the image of a vertex set, and two facts the library states with it.
Out-neighborhoods and Good Vertices
An oriented graph is a digraph with no loop and no pair of opposite arcs and .✦
The first out-neighborhood of a vertex of is the set of its out-neighbors, (1)✦ The second out-neighborhood of is the set of the vertices at directed distance exactly two from , (2)✦
A vertex of is good when its second out-neighborhood has at least as many vertices as its first.✦ Seymour’s second-neighborhood conjecture asserts that every oriented graph has a good vertex.
The Claim
Definition 1. Let be a digraph on a finite vertex set . The image of a set of vertices of is the set of the vertices that an arc from enters, those of included, (3)✦ We write for the set , the image of the image of .
Theorem 1. Let be a digraph on a finite vertex set and a vertex of . If is oriented, then (4)✦ If is a sink, a vertex with no out-neighbor, then is good: (5)✦
What Is Checked
The definition and the theorem are stated over a digraph on a finite vertex set with arbitrary arcs, the image (3), the out-neighborhoods (1) and (2), and good vertices, with orientation a hypothesis of (4) alone.