In September 2026, OpenAI released a preprint (OpenAI 2026) announcing a proof of Seymour’s second-neighbourhood conjecture, a long-standing problem in graph theory. The conjecture concerns a simple question: in a directed graph, must there always be a vertex that can reach at least as many new vertices in two steps as in one step?
Let us begin with the definitions.
A directed graph consists of a set of vertices and a collection of directed edges, called arcs. We write if there is an arc from vertex to vertex .
An oriented graph is a directed graph with no loops and no pairs of opposite arcs. Thus, for any two distinct vertices and , we may have , or , or neither, but not both.
For a vertex , its first out-neighbourhood is the set In other words, these are the vertices that can be reached from by following one directed edge.
The second out-neighbourhood consists of vertices whose shortest directed distance from is exactly two. Thus, a vertex belongs to if there is a directed path for some vertex , but there is no direct arc . The original vertex itself is also excluded.
Notice that we count vertices, not paths: if several different two-step paths lead to the same vertex, that vertex is counted only once.
For example, consider three vertices with arcs This is a directed cycle of length three. Each vertex has exactly one first out-neighbour and one second out-neighbour, so for all three vertices.
Here denotes the number of elements of a finite set .
Of course, the inequality need not hold for every vertex. For example, in the directed path , the vertex has one first out-neighbour but no second out-neighbours.
However, the vertex satisfies the inequality, since both its first and second out-neighbourhoods are empty.
More generally, a vertex with no outgoing arcs, called a sink, automatically satisfies the desired inequality.
But what happens if the graph has no sinks?
Seymour conjectured that the inequality must still hold for at least one vertex, regardless of the graph’s structure. The problem was recorded by Dean and Latka (Dean and Latka 1995) in 1995.
The conjecture attracted considerable attention, but even some seemingly simple cases turned out to be difficult.
A tournament is an oriented graph in which every pair of distinct vertices is joined by an arc in one direction. In other words, a tournament is obtained by choosing an orientation for every edge of a complete graph.
In 1996, Fisher (Fisher 1996) proved Seymour’s conjecture for tournaments. Havet and Thomassé (Havet and Thomassé 2000) subsequently gave a different proof based on a clever ordering of the vertices, known as a median order.
However, the general conjecture allows pairs of vertices with no arc between them, making the problem considerably harder.
In 2001, Kaneko and Locke (Kaneko and Locke 2001) proved the conjecture for oriented graphs whose minimum out-degree is at most . Here the out-degree of a vertex is simply the number of arcs leaving it.
Another direction was to prove a weaker inequality. In 2024, Huang and Peng (Huang and Peng 2024) showed that every oriented graph contains a vertex satisfying with the displayed constant understood approximately.
This was substantial progress, but the conjectured coefficient was .
The new OpenAI preprint (OpenAI 2026) claims to establish the full conjecture.
The theorem has no assumptions about connectivity or vertex degrees. It applies to every oriented graph, whether sparse or dense.
The bound is best possible. Indeed, in a directed cycle of length three, every vertex has exactly one first and one second out-neighbour, so the inequality holds with equality.
The restriction excluding opposite arcs is essential. If we allowed two vertices joined by arcs in both directions, then each vertex would have one first out-neighbour but no vertex at directed distance exactly two. Thus, neither vertex would satisfy the conclusion.
Let us briefly discuss the proof.
The authors argue by contradiction. They suppose that a counterexample exists and choose one with as few vertices as possible, and then with as few arcs as possible.
This minimality imposes surprisingly strong restrictions on how the out-neighbourhoods of sets of vertices can grow.
For a set of vertices, let denote the union of all first out-neighbourhoods of vertices in , and write .
By analysing what happens when certain arcs are deleted, and then replacing each vertex by a suitably large directed complete graph, the authors reduce the problem to proving that there cannot exist an oriented graph satisfying for every nonempty proper subset of its vertices, together with a natural condition on incoming arcs.
The final contradiction comes from a combinatorial argument involving pairs of vertices. The authors construct two families of ordered pairs and select them to maximize a certain quantity. They then use the displayed inequality to enlarge these families, removing conflicting pairs by means of a matching argument. The resulting families would have a larger value of the quantity that was already maximal, giving a contradiction.
A central ingredient is a general combinatorial lemma about removing conflicts between two collections of ordered pairs. Its proof uses linear algebra and matching theory.
The preprint also derives stronger weighted versions of the theorem, in which vertices carry nonnegative weights and neighbourhood sizes are replaced by sums of their weights.
The result remains available as a preprint, and independent scrutiny of the proof is important. If confirmed, it will settle a conjecture that has been studied for more than thirty years.
What makes the theorem particularly appealing is the simplicity of its statement. No matter how we orient the edges of a graph, provided that opposite arcs are excluded, there is always some vertex from which looking two steps ahead reveals at least as many new vertices as looking just one step ahead.