OctoInformBeta

OpenAI preprint, September 2026 · §2. From a counterexample to a strict subset inequality

Counterexamples, minimality and the subset conditions: Order and arc minimality, positive indegree, and three conditions on the images of a nonempty proper vertex set

A counterexample is a digraph with no good vertex.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Take an oriented graph and a vertex vv of it, and compare the number of out-neighbors of vv with the number of vertices at directed distance two from vv. Seymour’s second neighborhood conjecture says that every oriented graph has a vertex for which the second number is at least the first. These notes define its counterexamples and two senses in which a counterexample is smallest, together with four conditions on a digraph: one on the in-neighbors of its vertices, three on how a set of vertices grows when one follows the arcs out of it once and then twice.

Neighborhoods and Images

A digraph DD on a finite vertex set VV is given by its arcs between vertices of VV, an arc from uu to ww being written u→wu \to w. A digraph DD on VV is oriented when it has no loop v→vv \to v and no pair of opposite arcs u→wu \to w and w→uw \to u.✦

The first and second out-neighborhoods of a vertex vv of DD are the sets N1+(v)={u∈V:v→u},N2+(v)={w∈V:w≠v,v↛w,v→u→w for some u∈V}.N_1^+(v) = \{u \in V : v \to u\}, \qquad N_2^+(v) = \{w \in V : w \ne v,\ v \not\to w,\ v \to u \to w \text{ for some } u \in V\}.(1) A vertex vv of DD is good when |N1+(v)|≤|N2+(v)||N_1^+(v)| \le |N_2^+(v)|.✦ The second neighborhood conjecture for a digraph DD on VV is the assertion that some vertex of DD is good.✦

The image F(S)F(S) of a set SS of vertices of DD is the set of vertices that receive an arc from some vertex of SS, and F2(S)F^2(S) is the image of F(S)F(S): F(S)={y∈V:x→y for some x∈S},F2(S)=F(F(S)).F(S) = \{y \in V : x \to y \text{ for some } x \in S\}, \qquad F^2(S) = F(F(S)).(2)✦ The image F(S)F(S) may meet SS. A set SS of vertices of DD is proper when S≠VS \ne V.

The Claim

Definition 1. A digraph DD on a finite vertex set VV is a counterexample to the second neighborhood conjecture when |N2+(v)|<|N1+(v)|for every v∈V.|N_2^+(v)| < |N_1^+(v)| \ \text{for every } v \in V.(3)✦ A digraph DD on VV is order-minimal when |V|≤nfor every oriented counterexample on n≥1 vertices.|V| \le n \ \text{for every oriented counterexample on } n \ge 1 \text{ vertices}.(4)✦ The arc set of a digraph DD on VV is A(D)={(u,w)∈V×V:u→w},A(D) = \{(u, w) \in V \times V : u \to w\},(5)✦ and DD is arc-minimal when |A(D)|≤|A(D′)|for every oriented counterexample D′ on V.|A(D)| \le |A(D')| \ \text{for every oriented counterexample } D' \text{ on } V.(6)✦ A digraph DD on VV has positive indegree when every v∈V has an in-neighbor u→v.\text{every } v \in V \text{ has an in-neighbor } u \to v.(7)✦ A digraph DD on VV has nonempty out-boundaries when F(S)\S≠∅for every nonempty proper S⊆V.F(S) \setminus S \ne \emptyset \ \text{for every nonempty proper } S \subseteq V.(8)✦ A digraph DD on VV satisfies the subset deficit when |F2(S)\F(S)|<|F(S)\S|for every nonempty proper S⊆V.|F^2(S) \setminus F(S)| < |F(S) \setminus S| \ \text{for every nonempty proper } S \subseteq V.(9)✦ A digraph DD on VV has strict growth when |S|+|F2(S)|<2|F(S)|for every nonempty proper S⊆V.|S| + |F^2(S)| < 2\,|F(S)| \ \text{for every nonempty proper } S \subseteq V.(10)✦

What Is Checked

The conditions (3) to (10) are stated for a digraph DD on a finite vertex set VV, over its out-neighborhoods (1), its good vertices and the second neighborhood conjecture for DD, the images (2) of its proper sets of vertices, and, in the two minimality conditions, the oriented counterexamples on n≥1n \ge 1 vertices and on VV.