**Originator(s):**
P. Seymour (Princeton Univ.)

**Definitions:**
In a digraph *G*, let *N ^{+}(v)* denote the successors
of a vertex

**Conjecture:**
If *G* is a simple digraph with no cycle of length at most 2,
then *G* has a vertex *v* such that
|*N ^{++}(v)*| >= |

**Comments/Partial results:**
The special case when *G* is a tournament was conjectured by Dean
and proved by Fisher [F]. Fisher's proof uses Farkas' Lemma and averaging
arguments. A combinatorial proof appears in [HT] using median orders, where a
*median order* of a tournament *T* is a transitive tournament
on *V(T)* having the most edges in common with *T*. This proof
obtains not one but two of the desired vertices.

Kaneko and Locke [KL] proved this conjecture for digraphs having a vertex with outdegree at most 6. Godbole, Cohn, and Wright [GCW] have proved that the conjecture holds for almost all digraphs.

Chen, Shen, and Yuster [CSY] proved that for every digraph, there is a vertex
*v* such that |*N ^{++}(v)*| >= r|

Seymour's conjecture implies a special case of the Caccetta-Häggkvist Conjecture.

**References:**

[CS] Chen, G.; Shen, J.; Yuster, R.
Second neighborhood via first neighborhood in digraphs,
Annals of Combinatorics, 7 (2003), 15--20.

[F] Fisher, David C.
Squaring a tournament: a proof of Dean's conjecture.
J. Graph Theory 23 (1996), no. 1, 43--48.

[GCW] Godbole, A; Cohn, Z; Wright, E.
Probabilistic Versions of Seymour's Distance Two Conjecture, to appear.

[HT] Havet, F.; Thomassé, S.
Median orders of tournaments: a tool for the second neighborhood problem and
Sumner's conjecture. J. Graph Theory 35 (2000), no. 4, 244--256.

[KL] Kaneko, Yoshihiro; Locke, Stephen C.
The minimum degree approach for Paul Seymour's distance 2 conjecture.
Proceedings of the Thirty-second Southeastern International Conference on Combinatorics, Graph Theory and Computing (Baton Rouge, LA, 2001).
Congr. Numer. 148 (2001), 201--206.