An arc--nonedge defect identity for Sullivan-1

Definitions and mathematical statement

Consider a nonempty finite oriented graph $D=(V,E)$: there are no loops, no parallel arcs, and no pair of oppositely directed arcs. For $v\in V$, its in-neighbourhood is $N^-(v)=\{u:u\to v\}$ and its first out-neighbourhood is $N^+(v)=\{u:v\to u\}$. Its second out-neighbourhood is \[ N_2^+(v)=\left(\bigcup_{u\in N^+(v)}N^+(u)\right) \setminus\left(N^+(v)\cup\{v\}\right). \] Thus its members are at shortest directed-path distance exactly two. The union eliminates multiple routes to an endpoint, and the subtraction eliminates immediate out-neighbours.

The compromise conjecture, Conjecture 6.6 in the AIM source, asks whether every such graph has a vertex $v$ with \[ |N_2^+(v)|\ge |N^-(v)|. \] The comparison is with incoming neighbours, while the two-step reachability is in the outgoing direction. Reversing this direction in just one of the two definitions would change the conjecture. The witnessing vertex can depend on $D$, and neither connectivity nor degree regularity is assumed. Sources, having indegree zero, are immediate witnesses, so a counterexample would have positive indegree at every vertex. Opposite arcs remain forbidden even in that case. The target counts distinct second neighbours, not the number of directed two-edge paths or the number of vertices at out-distance at most two.

Short English statement

Must every oriented graph have a vertex with at least as many second out-neighbours as incoming neighbours?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 20001046 (AIM-COMBINATORICS-0171), AIM Workshop Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 American Institute of Mathematics, The Caccetta-Haggkvist conjecture, item 6.6. Original workshop question underlying AIM-COMBINATORICS-0171. https://aimath.org/WWN/caccetta/caccetta.pdf.