A collision budget for Eulerian second neighborhoods

Definitions and mathematical statement

Let $D=(V,E)$ be a finite simple oriented graph, with no loops or opposite arcs. It is Eulerian in the degree sense when $d^+(v)=d^-(v)$ for every vertex $v$; isolated vertices and separate components are allowed. Here $d^+(v)$ and $d^-(v)$ are the numbers of outgoing and incoming neighbours. Let $N_2^+(v)$ be the set of vertices at shortest directed distance two from $v$, excluding both $v$ itself and its immediate outgoing neighbours. Only distinct vertices are counted.

The proposed aggregate second-neighbourhood inequality is \[ \sum_{v\in V}|N_2^+(v)| \ \ge\ \sum_{v\in V}d^+(v)=|E|. \] Thus the number of ordered pairs $(v,w)$ at directed distance exactly two should be at least the number of arcs. A pair admitting several two-edge paths contributes only once to the left-hand side, and a pair joined directly by an arc never contributes there.

The problem asks for this inequality for every Eulerian oriented graph, not just a vertex whose individual second-neighbourhood is large. Balanced indegree and outdegree are required vertex by vertex; equality of the total indegree and total outdegree, which holds for every digraph, is insufficient. Connectedness can equivalently be imposed component by component since both sides add across components. The unweighted simple-graph convention prevents multiplicity from changing the degree balance while leaving neighbourhood cardinalities unchanged.

Short English statement

Does every Eulerian oriented graph have at least as many ordered distance-two pairs as arcs?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 20001058 (AIM-COMBINATORICS-0183), 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. Original workshop question underlying AIM-COMBINATORICS-0183. https://aimath.org/WWN/caccetta/caccetta.pdf.