OctoInformBeta

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

Lemma 2.2: An oriented graph with no good vertex, of minimum order and then fewest arcs, has |F2(S)\F(S)|<|F(S)\S||F^2(S) \setminus F(S)| < |F(S) \setminus S| for ∅≠S⊊V\emptyset \neq S \subsetneq V

Minimal counterexamples have positive indegree and the subset deficit.

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

A digraph DD on a finite vertex set VV, with u→wu \to w for an arc, is an oriented graph 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 neighborhood N1+(v)N_1^+(v) of a vertex vv of DD is the set of its out-neighbors✦, and the second neighborhood N2+(v)N_2^+(v) is the set of vertices at directed distance exactly two from vv: N1+(v)={u:v→u},N2+(v)={w:w≠v,v↛w,v→u→w for some u}.N_1^+(v) = \{u : v \to u\}, \qquad N_2^+(v) = \{w : w \neq v,\ v \not\to w,\ v \to u \to w \text{ for some } u\}.(1)✦ A vertex vv is good when |N1+(v)|≤|N2+(v)||N_1^+(v)| \le |N_2^+(v)|, and Seymour’s second-neighborhood conjecture asserts that every oriented graph has a good vertex. A counterexample on VV is a digraph on VV with no good vertex✦, and an oriented counterexample is a counterexample that is an oriented graph.

The lemma looks at oriented counterexamples that are as small as possible, first in their number of vertices and then in their number of arcs. The question is what this minimality forces on a set of vertices and on the vertices it reaches along one arc and along two.

Images and Minimality

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, F(S)={y:x→y for some x∈S}F(S) = \{y : x \to y \text{ for some } x \in S\}, and F2=F∘FF^2 = F \circ F.✦ The set SS is not removed, so F(S)F(S) may meet SS.

Write [n][n] for the standard set of nn vertices. A digraph DD on VV has minimum order when |V|≤nfor every n≥1 and every oriented counterexample on [n].|V| \le n \quad \text{for every } n \ge 1 \text{ and every oriented counterexample on } [n].(2)✦

The arc set A(D)A(D) of a digraph DD on VV is the set of pairs (u,w)(u, w) of vertices with u→wu \to w.✦ A digraph DD on VV has the fewest arcs on VV when |A(D)|≤|A(D′)|for every oriented counterexample D′ on V.|A(D)| \le |A(D')| \quad \text{for every oriented counterexample } D' \text{ on } V.(3)✦

The Claim

Theorem 1. Let DD be an oriented counterexample on a finite vertex set VV.

  • If DD has minimum order, then DD has nonempty boundary: F(S)\S≠∅for every S with ∅≠S⊊V.F(S) \setminus S \neq \emptyset \quad \text{for every } S \text{ with } \emptyset \neq S \subsetneq V.(4)✦

  • If DD has nonempty boundary, then DD has positive indegree: for every v∈V there is u∈V with u→v.\text{for every } v \in V \text{ there is } u \in V \text{ with } u \to v.(5)✦

  • If DD has nonempty boundary and has the fewest arcs on VV, then DD has the subset deficit: |F2(S)\F(S)|<|F(S)\S|for every S with ∅≠S⊊V.|F^2(S) \setminus F(S)| < |F(S) \setminus S| \quad \text{for every } S \text{ with } \emptyset \neq S \subsetneq V.(6)✦

  • If VV is nonempty, then for some n≥1n \ge 1 there is an oriented counterexample D′D' on [n][n] such that D′ has the fewest arcs on [n], nonempty boundary and positive indegree.D' \text{ has the fewest arcs on } [n], \text{ nonempty boundary and positive indegree}.(7)✦

In the paper, the result reads: if DD is a finite nonempty oriented graph with |N1+(v)|>|N2+(v)||N_1^+(v)| > |N_2^+(v)| for every vertex vv, chosen with minimum order and, subject to that, with the minimum number of arcs among all graphs with this property, then DD is strongly connected, every vertex has positive indegree, and |F2(S)\F(S)|<|F(S)\S||F^2(S) \setminus F(S)| < |F(S) \setminus S| for every SS with ∅≠S⊊V\emptyset \neq S \subsetneq V.

What Is Checked

The lemma is stated over oriented counterexamples on a finite vertex set, with their first and second neighborhoods (1), the image FF and the arc set A(D)A(D), and over the conditions of minimum order (2), fewest arcs (3), nonempty boundary (4), positive indegree (5) and the subset deficit (6).