we-solve (beta)

Math-1116 · mathematics · Graph theory

Seymour's Second Neighbourhood Conjecture

Status Open · unsolvedmath.comLLM status Open unverified

Statement

Definitions and mathematical statement

Let $D=(V,A)$ be a finite nonempty oriented graph: it has no loops, no parallel arcs, and never contains both $uv$ and $vu$. The first outneighbourhood of $v$ is $N^+(v)=\{u\in V:vu\in A\}$. Define its second outneighbourhood by \[ N^{++}(v)=\{w\in V\setminus(\{v\}\cup N^+(v)): \exists u\in V\text{ with }vu,uw\in A\}. \] Thus $N^{++}(v)$ consists of vertices at directed distance exactly two from $v$, not all vertices reachable by a two-step walk. A vertex already in $N^+(v)$ is excluded even if it also has such a walk. Both sets count distinct vertices, without multiplicity.

Seymour's second neighbourhood conjecture asks whether every finite nonempty oriented graph has at least one vertex $v$ satisfying \[ |N^+(v)|\le |N^{++}(v)|. \] The desired vertex may depend on the entire orientation. There is no claim that every vertex, or a prescribed vertex, satisfies the inequality. A sink has no outneighbours and therefore already satisfies it with both sides zero.

The orientation condition cannot simply be dropped: in the complete symmetric digraph every other vertex is a first outneighbour, leaving no second outneighbours in the exact-distance sense. The asserted bound has coefficient exactly one; a positive lower ratio strictly below one would be a different, weaker statement. All finite orders and all underlying simple graphs are included.

Short English statement

Must every oriented graph contain a vertex with at least as many vertices at outward distance two as at outward distance one?

Sources

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 1

Math-1116-A1 · Literature report · LLM-generated · unknown ·

OpenAI claim summary for Math-1116

Seymour second neighborhoods: The paper claims that every finite nonempty oriented graph has a vertex whose second out-neighborhood is at least as large as its first. The second neighborhood excludes vertices already reachable in one step. The parameters, regularity assumptions and normalization in this question are retained in applying that assertion.

With the hypotheses and conventions above, the claimed result addresses the whole mathematical assertion on this page.

Seymour's Second Neighbourhood Conjecture

OpenAI's claim

Seymour second neighborhoods: The paper claims that every finite nonempty oriented graph has a vertex whose second out-neighborhood is at least as large as its first. The second neighborhood excludes vertices already reachable in one step.

Mathematical statement of the claimed result

Mathematical claim 1.
For a nonempty finite oriented graph $D$, with no loops or oppositely directed pair of edges, let $N_1^+(v)$ be the out-neighbors and $N_2^+(v)$ the vertices at directed distance exactly two. The claimed theorem gives \[\exists v\in V(D):\quad|N_1^+(v)|\le|N_2^+(v)|.\] For triangle-free $D$ a corollary yields a vertex with $d^+(v)\le|Z(v)|$ and $n-1\ge2d^+(v)+d^-(v)$, where $Z(v)$ consists of non-neighbors excluding $v$. Hence $\delta^+\ge n/3$ and $\delta^-\ge n/3$ force a directed triangle; a digraph regular in both directions with degree $r$ and girth four has $n\ge3r+1$. These consequences require the specified in-degree conditions and do not give the full out-degree-only Caccetta--Häggkvist assertion.

Outline of the argument

Seymour second neighborhoods: A smallest counterexample is pruned to yield strict neighborhood inequalities for all proper vertex sets. Replacing vertices by transitive tournaments strengthens these to a discrete concavity inequality. Extremal families of ordered pairs and an augmented bipartite matching are then controlled by two factorizations of one matrix, contradicting that inequality.

Formal verification

Family 173 describes Lean coverage for the exact second-out-neighborhood inequality for a suitable vertex of every finite nonempty oriented graph.

Seymour second neighborhoods: The manuscript links SeymourSecondNeighborhood.lean (declaration OAI.SeymourSecondNeighborhood.exists_goodVertex).

The documented selection includes this manuscript’s main assertion; that assertion retains the restrictions stated above.

This site has not run the Lean development. These links describe OpenAI’s selected formal statements and should be read with their stated scope.

Status caveat

OpenAI reports that an internal model produced the manuscripts. Their arguments have not been independently verified as proofs by this site. Any portion outside the documented formal scope may contain mistakes, and the catalogue label reports the announced mathematical claim.

Sources

Go to contribution →