Finding a vertex whose second neighborhood is at least as large as its first

← All digests

Family 173 · Combinatorics
Importance 5/5 · Provisional editorial rating
Sources consulted 2026-10-11

1. The question

Imagine a network of one-way links. From a starting point, some vertices are reachable in one step. Others become reachable for the first time in two steps. Must there be a starting point for which the second group is at least as large as the first?

The network may be irregular, disconnected or sparse. The only restriction, beyond finiteness, is that a pair of vertices cannot carry links in both directions. Seymour’s second-neighborhood conjecture predicts that such a starting point always exists.

The manuscript claims the conjecture in full. Its argument turns a supposed failure at every vertex into an impossible expansion rule for all vertex subsets. A separate pruning principle for pairs of sets supplies the contradiction. The paper also records weighted versions and consequences for short directed cycles.

2. Background and essential definitions

An oriented graph is obtained by assigning directions to the edges of a simple undirected graph. It has no loops, repeated arcs or opposite pair of arcs. Write $v\to u$ for an arc from $v$ to $u$.

The first out-neighborhood is

$$N_1^+(v)=\{u:v\to u\}.$$

The exact second out-neighborhood is

$$N_2^+(v)=\{w\notin\{v\}\cup N_1^+(v): \text{ some }u\text{ satisfies }v\to u\to w\}.$$

The word “exact” matters. A vertex already reachable in one step does not count in the second group, even if it is also reachable in two steps. Each endpoint counts once, regardless of how many two-step paths reach it.

For example, a directed triangle has one first and one exact second out-neighbor at every vertex. A sink, meaning a vertex with no outgoing arcs, has neither; it satisfies the desired inequality trivially. In a directed chain, the last vertex is a sink, while an interior vertex sufficiently far from the end has one neighbor of each kind.

The outdegree $d^+(v)$ is $|N_1^+(v)|$. The indegree $d^-(v)$ counts vertices with arcs into $v$. A tournament is an oriented graph with an arc between every pair of distinct vertices. It is a particularly dense special case, not the general setting of the claim.

3. Development history and previous partial results

The conjecture was recorded by Dean and Latka in 1995. The tournament case, also known as Dean’s conjecture, was proved by Fisher in 1996 using a probability distribution obtained from linear programming duality. Havet and Thomassé later gave a combinatorial proof using specially chosen vertex orders.

Those results suggested that the inequality was compatible with very dense directed networks. Further work extended it to tournaments with particular missing-edge patterns, such as a matching or certain stars. These patterns allow some of the tournament structure to remain available even though the underlying graph is no longer complete.

Another approach restricted degrees. Kaneko and Locke established the conjecture when the minimum outdegree is at most six. A 2026 computer-assisted manuscript treats minimum outdegree seven. Such results cover all graphs with a sufficiently low-degree vertex, but leave arbitrary large minimum degrees untouched.

A third line weakened the desired comparison to

$$|N_2^+(v)|\geq\lambda|N_1^+(v)|$$

for a universal constant $\lambda<1$. Chen, Shen and Yuster obtained approximately $0.657298$. Huang and Peng raised the theoretical bound to approximately $0.715538$, and reported a computational bound of $0.74530$. The original conjecture asks for the endpoint $\lambda=1$.

Results for orientations of random graphs and for sufficiently dense graphs supplied other substantial partial cases. The manuscript’s principal structural predecessors are the minimal-counterexample and graph-product methods of Brantner, Brockman, Kay and Snively, together with Seacrest’s subset formulation. The new argument claims to combine a strengthened subset inequality with a pruning lemma that is valid for arbitrary finite binary relations.

4. What the new manuscripts claim

The unweighted theorem

For every nonempty finite oriented graph, the manuscript states that some vertex $v$ satisfies

$$|N_1^+(v)|\leq|N_2^+(v)|.$$

There is no connectivity assumption and no lower or upper degree restriction. The statement is existential: it guarantees at least one suitable vertex, rather than the inequality at every vertex.

Two different weighted conclusions

For a nonnegative vertex weighting $\eta$, write

$$\eta(S)=\sum_{x\in S}\eta(x).$$

The paper invokes Seacrest’s established weighted equivalences to obtain two consequences with different quantifier orders. For every specified weighting, there is a vertex satisfying

$$\eta(N_1^+(v))\leq\eta(N_2^+(v)).$$

Conversely, there exists some nonnegative weighting of total mass one for which this inequality holds at every vertex simultaneously. The weights in that second conclusion may include zeros. It does not say that every weighting works everywhere.

The manuscript also states the corresponding arc-weighted form through the same earlier equivalences. These equivalences are credited as existing results; the new input is the claimed unweighted theorem for all oriented graphs.

A directed-triangle consequence

If an oriented graph on $n$ vertices has both minimum indegree and minimum outdegree at least $n/3$, the manuscript concludes that it contains a directed triangle.

To see the connection, suppose there is no directed triangle. Every exact second out-neighbor of $v$ must then be a non-neighbor: an arc back into $v$ would close a triangle, while an arc out of $v$ is excluded by the exact-distance definition. For the vertex supplied by the main theorem, counting the disjoint groups gives

$$n-1\geq2d^+(v)+d^-(v).$$

Both degree lower bounds would make the right side at least $n$, an impossibility. This consequence uses both directions of degree; it is not the general one-sided minimum-outdegree conjecture about short cycles.

5. Why the advance matters

Importance: 5/5. The claim resolves a central and elementary-to-state problem in directed graph theory. Its simplicity is deceptive: local two-step reachability can overlap heavily with immediate reachability, so an ordinary averaging argument does not directly produce the desired vertex.

The assertion also holds without the global regularity used in many earlier partial cases. Reaching the exact factor one unifies tournament, bounded-degree and approximate-ratio results under a single theorem.

The weighted consequences make the comparison more flexible. Vertices may represent unequal amounts of mass rather than indistinguishable units, while the existence of a favorable viewpoint survives. The new pruning principle is potentially interesting beyond this specific conjecture because its statement concerns general finite relations. The rating reflects the complete conjecture and these structural connections, conditional on the manuscript’s claims.

6. The main idea

Strengthen a local failure into a subset rule

For a vertex subset $S$, let

$$F(S)=\{y:\text{ some }x\in S\text{ has }x\to y\}.$$

This is the union of outgoing neighbors; it does not automatically remove vertices of $S$. Applying $F$ twice gives all endpoints of two-step walks starting in $S$, again without the exact-distance exclusions used for an individual neighborhood.

Assume every vertex violates the desired theorem and choose a counterexample first with as few vertices, then as few arcs, as possible. The manuscript uses carefully chosen arc deletions to deduce a strict deficit for every nonempty proper subset. It then replaces each vertex by a sufficiently large transitively oriented complete graph, with all arcs between blocks following the original directions.

This enlarged graph is claimed to satisfy

$$|U|+|F^2(U)|<2|F(U)|$$

for every nonempty proper subset $U$. Thus its first image would always be strictly larger than the average size of the starting set and the second image. The task becomes ruling out such a universal expansion pattern.

Compare two families of ordered pairs

Work in the square of the vertex set. An ordered pair has two coordinates, and each coordinate can advance along a graph arc while the other stays fixed. The argument chooses two families of pairs whose respective coordinate images do not overlap. Both families must contain the diagonal pairs $(v,v)$.

Let $M$ be the combined size of the two families and let $d$ count positions left uncovered by their images. Choose compatible families maximizing $M+d$. Applying the subset inequality to their columns and rows produces larger prospective families, with combined size exceeding $M+2d$.

The prospective families can conflict. Simply deleting every conflict might destroy the gain. The pruning lemma instead restores compatibility while preserving the diagonal and charging its deletion cost partly to positions that remain uncovered afterward.

If $d'$ is that new uncovered count, the stated cost is at most $d+d'$. The new objective therefore exceeds

$$M+2d-(d+d')+d'=M+d,$$

contradicting maximality. The cancellation explains why the uncovered positions belong in the objective: they compensate for part of the later pruning loss.

The lemma itself uses a matching construction and linear algebra, comparing two ways to advance the coordinates. This is the additional mechanism that allows the local neighborhood problem to be closed by a global extremal argument.

7. Scope, limitations, and open questions

The orientation restriction is indispensable to the stated theorem. With two vertices joined in both directions, each vertex has one first out-neighbor and no exact second out-neighbor. Such a directed graph is excluded from the outset.

The finite, nonempty hypothesis also remains part of the statement. The paper does not claim an infinite-graph extension, nor that a positive fraction of all vertices must satisfy the inequality. A sink can be the simplest witness, so the theorem alone does not imply a large nontrivial expanding neighborhood.

The weighted results permit zero weights. Requiring a strictly positive weighting that works at every vertex would be a stronger assertion and is not the stated consequence.

Finally, the directed-triangle corollary assumes both indegree and outdegree lower bounds. Removing the indegree hypothesis leads to a different and stronger short-cycle problem. The manuscript resolves the second-neighborhood statement, not every related conjecture about directed cycles.

8. Sources and further reading

The manuscript’s opening two pages give the exact neighborhood convention and the extremal strategy. Its later sections state the weighted quantifiers and the directed-cycle consequences separately.

Primary related sources include Huang–Peng’s approximate-ratio improvement, the minimum-outdegree-seven manuscript, Seacrest’s subset approach, and Seacrest’s arc-weighted equivalences. M1’s bibliography also identifies the original tournament proofs and the graph-product work on which its reduction builds.

Source manuscripts

• M1. OpenAI, A proof of Seymour’s second-neighborhood conjecture (September 23, 2026).

Sources consulted on 11 October 2026 at repository revision fd4aeeb. Download the manuscript citations.