The Setting
Take a digraph on a finite vertex set , written with arrows, for an arc. The image of a set of vertices is the set of vertices that receive an arc from some vertex of , (1)✦ The image may meet . The second image is the map .
Fix a set of vertices. Its image splits into , the part inside , and , the vertices that reaches outside itself; the vertices reached from in two steps but not in one form . The subset deficit is the statement that (2) holds for every nonempty proper vertex set , a vertex set being proper when it is not all of .
The deficit potential of is the function on vertex sets that counts, for a set , the vertices receiving an arc from and lying neither in nor in : (3)✦
The arc-deletion step follows along subsets of , adding at each step a nonempty set of vertices of not yet in .
Counterexamples
The first neighborhood of a vertex of is the set of its out-neighbors✦, and the second neighborhood of is the set of vertices at directed distance exactly two from : (4)✦
A vertex is good when . A digraph on is a counterexample to Seymour’s second-neighborhood conjecture when it has no good vertex: (5)✦
A digraph on is oriented when it has no loop and no pair of opposite arcs and .✦ The arc set of is the set of ordered pairs of vertices with .✦ A digraph on is arc-minimal when no oriented counterexample on has fewer arcs: for every oriented counterexample on .✦
The subdigraph induced on a vertex set is the digraph on whose arcs are the arcs of with and in .✦
The Claim
Theorem 1. Let be a digraph on a finite vertex set and a set of vertices, with , and the deficit potential of as above.
If is an oriented, arc-minimal counterexample, then every proper subset of has a nonempty subset of with (6)✦
For vertex sets , and with disjoint from , (7)✦ for , the first terms of the two sides are and .
If is a nonempty vertex set and a function from vertex sets to the nonnegative integers with such that every proper subset of has a nonempty subset of with , then (8)✦
At , the deficit potential takes the value (9)✦
If is a counterexample and , then the induced subdigraph is a counterexample: with the neighborhoods taken in , (10)✦
In the paper, the result reads: for , deleting the arcs from to yields a nonempty with , where and ; summing from gives , and ; strong connectivity is argued with a terminal strongly connected component, which carries a smaller counterexample.
What Is Checked
The claim is stated over finite digraphs and the images of their vertex sets, the first and second neighborhoods and the counterexamples they define, oriented graphs, arc-minimality through the arc set, the deficit potential and the induced subdigraph .