OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction

Oriented graphs and exact out-neighborhoods: Oriented graphs, the first and second out-neighborhoods N1+(v)N_1^+(v) and N2+(v)N_2^+(v) of a vertex, and the condition |N1+(v)|≤|N2+(v)||N_1^+(v)| \le |N_2^+(v)| that makes it good

Good vertices and the second-neighborhood conjecture for a digraph.

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 vertex vv of a finite oriented graph. Some vertices are reached from vv by a single arc; others are reached by a directed path of two arcs and not by one. Seymour’s second-neighborhood conjecture asserts that every finite oriented graph has a vertex vv with at least as many vertices of the second kind as of the first.

The library defines the notions this conjecture is made of, for a digraph on a finite vertex set: an oriented graph, the first and second out-neighborhoods N1+(v)N_1^+(v) and N2+(v)N_2^+(v) of a vertex vv, a good vertex, and the second-neighborhood conjecture for a single digraph, the property that Seymour’s conjecture asserts of every finite oriented graph.

The Definition

Definition 1. Let DD be a digraph on a finite vertex set VV, with u→wu \to w for an arc from uu to ww; loops v→vv \to v are allowed.

The digraph DD is oriented when it has no loop and no pair of opposite arcs: v↛vandw↛u whenever u→w,for all u,v,w∈V.v \not\to v \quad\text{and}\quad w \not\to u \text{ whenever } u \to w, \qquad \text{for all } u, v, w \in V.(1)✦

The first out-neighborhood N1+(v)N_1^+(v) of a vertex vv of DD is the set of the out-neighbors of vv: N1+(v)={u∈V:v→u}.N_1^+(v) = \{u \in V : v \to u\}.(2)✦

The second out-neighborhood N2+(v)N_2^+(v) of a vertex vv of DD is the set 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\}.(3)✦

A vertex vv of DD is good when its second out-neighborhood is at least as large as its first: |N1+(v)|≤|N2+(v)|.|N_1^+(v)| \le |N_2^+(v)|.(4)✦

The digraph DD satisfies the second-neighborhood conjecture when it has a good vertex: |N1+(v)|≤|N2+(v)|for some v∈V.|N_1^+(v)| \le |N_2^+(v)| \quad \text{for some } v \in V.(5)✦

What Is Checked

The five definitions are stated over a digraph DD on a finite vertex set VV with any set of arcs, loops included, and (2) to (4) over a vertex vv of DD as well; the neighborhoods N1+(v)N_1^+(v) and N2+(v)N_2^+(v), good vertices and the second-neighborhood conjecture (5) are defined for every such digraph, oriented or not.