OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction

The image operator: The image F(S)F(S) of a vertex set; in an oriented graph N2+(v)=F2({v})\F({v})N_2^+(v) = F^2(\{v\}) \setminus F(\{v\}), and a sink is a good vertex

The second out-neighborhood as a difference of images.

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 a digraph DD on a finite vertex set VV: a set of arcs u→wu \to w between vertices of VV, in which a loop v→vv \to v and a pair of opposite arcs may occur. These notes give the operator that takes one step, the image of a vertex set, and two facts the library states with it.

Out-neighborhoods and Good Vertices

An oriented graph is a digraph with no loop v→vv \to v and no pair of opposite arcs u→wu \to w and w→uw \to u.✦

The first out-neighborhood of a vertex vv of DD is the set N1+(v)N_1^+(v) of its out-neighbors, N1+(v)={u∈V:v→u}.N_1^+(v) = \{u \in V : v \to u\}.(1)✦ The second out-neighborhood of vv is the set N2+(v)N_2^+(v) of the vertices at directed distance exactly two from vv, N2+(v)={w∈V:w≠v,v↛w, and v→u→w for some u∈V}.N_2^+(v) = \{w \in V : w \neq v,\ v \not\to w, \text{ and } v \to u \to w \text{ for some } u \in V\}.(2)✦

A vertex vv of DD is good when its second out-neighborhood has at least as many vertices as its first.✦ Seymour’s second-neighborhood conjecture asserts that every oriented graph has a good vertex.

The Claim

Definition 1. Let DD be a digraph on a finite vertex set VV. The image F(S)F(S) of a set SS of vertices of DD is the set of the vertices that an arc from SS enters, those of SS included, F(S)={y∈V:x→y for some x∈S}.F(S) = \{y \in V : x \to y \text{ for some } x \in S\}.(3)✦ We write F2(S)F^2(S) for the set F(F(S))F(F(S)), the image of the image of SS.

Theorem 1. Let DD be a digraph on a finite vertex set VV and vv a vertex of DD. If DD is oriented, then N2+(v)=F2({v})\F({v}).N_2^+(v) = F^2(\{v\}) \setminus F(\{v\}).(4)✦ If vv is a sink, a vertex with no out-neighbor, then vv is good: |N1+(v)|≤|N2+(v)|.|N_1^+(v)| \le |N_2^+(v)|.(5)✦

What Is Checked

The definition and the theorem are stated over a digraph on a finite vertex set with arbitrary arcs, the image (3), the out-neighborhoods (1) and (2), and good vertices, with orientation a hypothesis of (4) alone.