Seymour’s Second Neighborhood Conjecture for Oriented Graphs of Order at Most Seven and Split–Twin Extensions

Stanisław M. S. Halkiewicz · 2026

Read Seymour’s Second Neighborhood Conjecture for Oriented Graphs of Order at Most Seven and Split–Twin Extensions by Stanisław M. S. Halkiewicz (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-21563.txt.

Introduction

Stanisław M. S. Halkiewicz tests a long-standing conjecture about directed graphs on the smallest cases. The conjecture, from Seymour, concerns the second neighborhood of a vertex: the nodes two steps out along arrows. It claims some vertex always has at least as many nodes two steps out as one step out.

The author settles the claim for oriented graphs with up to seven vertices. Split-twin extensions then carry the result further. Small-case proofs matter because they expose the patterns a general proof must use. They also give computers and humans firm ground at the base of a hard problem.

Catalog record

CREATORStanisław M. S. Halkiewicz
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE20 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-21563

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Seymour’s Second Neighborhood Conjecture for Oriented Graphs of Order at Most Seven and Split–Twin Extensions Stanisław M. S. Halkiewicz Abstract For an oriented graph D D , let N 1 + ​ ( v ) N_{1}^{+}(v) denote the out-neighborhood of a vertex v v , and let N 2 + ​ ( v ) N_{2}^{+}(v) be the set of vertices reachable from v v by a directed path of length two that are neither out-neighbors of v v nor equal to v v . The Second Neighborhood Conjecture of Seymour asserts that every oriented graph contains a vertex v v with | N 2 + ​ ( v ) | ⩾ | N 1 + ​ ( v ) | |N_{2}^{+}(v)|\geqslant|N_{1}^{+}(v)| . Equivalently, if one defines the second neighborhood invariant Δ ⁡ ( D ) = max v ∈ V ⁡ ( D ) ⁡ ( | N 2 + ​ ( v ) | − | N 1 + ​ ( v ) | ) , \Delta(D)=\max_{v\in V(D)}\bigl(|N_{2}^{+}(v)|-|N_{1}^{+}(v)|\bigr), the conjecture asserts that Δ ⁡ ( D ) ⩾ 0 \Delta(D)\geqslant 0 for all oriented graphs. We prove by exhaustive computation that Δ ⁡ ( D ) ⩾ 0 \Delta(D)\geqslant 0 for every oriented graph on at most seven vertices. We also introduce a local graph operation, called a split–twin extension, and prove that it preserves the inequality Δ ⁡ ( D ) ⩾ 0 \Delta(D)\geqslant 0 . Consequently, Δ ⁡ ( D ) ⩾ 0 \Delta(D)\geqslant 0 holds for infinite inductively generated families of oriented graphs. 1 Introduction Let D be an oriented graph. For a vertex v\in V(D) , denote by N_{1}^{+}(v) its out-neighborhood, and by N_{2}^{+}(v) the set of vertices reachable from v by a directed path of length two that are neither out-neighbors of v nor equal to v . We refer to N_{2}^{+}(v) as the set of new second out-neighbors of v . The Second Neighborhood Conjecture , formulated by Seymour, asserts that every oriented graph contains a vertex v satisfying |N_{2}^{+}(v)|\geqslant|N_{1}^{+}(v)|. This conjecture has attracted considerable attention and is known to hold in a number of special cases, most notably for tournaments [ 5 , 3 , 6 ] . Further partial results and related investigations appear in [ 7 , 8 , 2 , 9 ] . Probabilistic aspects of the conjecture are an emergin and promising avenue in the topic (e.g. see [ 10 , 4 , 1 ] ). In particular, random oriented graphs are known to satisfy the second neighborhood property with high probability, suggesting that potential counterexamples, if they exist, must exhibit strong structural constraints [ 4 ] . [ 11 ] wrote about possible structural properties of counterexamples to the discussed conjecture. It is convenient to encode the conjecture via the graph invariant \Delta(D)=\max_{v\in V(D)}\bigl(|N_{2}^{+}(v)|-|N_{1}^{+}(v)|\bigr), so that Seymour’s conjecture is equivalent to the assertion that \Delta(D)\geqslant 0 for all oriented graphs. Despite sustained effort, the conjecture remains open in full generality and no general inductive mechanism is currently known that extends the validity of the conjecture from small graphs to arbitrarily large ones. The purpose of this paper is twofold. First, we provide a complete computational verification of the inequality \Delta(D)\geqslant 0 for all oriented graphs on at most seven vertices. Second, we introduce an inductive graph operation, which we call the split–twin extension , and prove that it preserves the nonnegativity of \Delta(D) . Together, these establish the second neighborhood property for all oriented graphs of order at most seven and for all graphs obtained from them by iterated split–twin extensions. 2 Preliminaries An oriented graph is a directed graph with no loops and no pair of oppositely oriented edges. Throughout the paper, all graphs are finite. Let D be an oriented graph with vertex set V(D) . For a vertex v\in V(D) , the out-neighborhood of v is defined as N_{1}^{+}(v)=\{u\in V(D):v\to u\}. The new second out-neighborhood of v is the set N_{2}^{+}(v)=\bigl\{w\in V(D)\setminus(N_{1}^{+}(v)\cup\{v\}):\exists\,u\in V(D)\text{ with }v\to u\to w\bigr\}. That is, N_{2}^{+}(v) consists of vertices reachable from v by a directed path of length two that are neither out-neighbors of v nor equal to v . We measure the discrepancy between first and second out-neighborhoods via the following quantity. Definition 1 . For a vertex v\in V(D) , the second neighborhood margin of v is \mathrm{margin}(v)=|N_{2}^{+}(v)|-|N_{1}^{+}(v)|. The second neighborhood invariant of D is \Delta(D)=\max_{v\in V(D)}\mathrm{margin}(v). Note that Seymour’s Second Neighborhood Conjecture is equivalent to the assertion that \Delta(D)\geqslant 0 for every oriented graph D . Definition 2 . Let D be an oriented graph. A vertex v\in V(D) is called a Seymour vertex if |N_{2}^{+}(v)|\geqslant|N_{1}^{+}(v)|, or equivalently, if \mathrm{margin}(v)\geqslant 0 . Equivalently, D contains a Seymour vertex if and only if \Delta(D)\geqslant 0 . Observation 3 . If v\in V(D) has outdegree zero, then |N_{1}^{+}(v)|=|N_{2}^{+}(v)|=0 , and hence \mathrm{margin}(v)=0 . Proof. If v has outdegree zero, then N_{1}^{+}(v)=\varnothing . Since there is no vertex u with v\to u , there is no directed path of length two starting at v , and thus N_{2}^{+}(v)=\varnothing as well. ∎ Accordingly, throughout this paper we restrict attention to oriented graphs with minimum outdegree at least one, as vertices of outdegree zero trivially satisfy the second neighborhood inequality. 3 Computational Verification for Small Graphs We begin by establishing the Second Neighborhood Conjecture for all oriented graphs of small order by exhaustive computation. Theorem 4 . Let D be an oriented graph on at most seven vertices. Then \Delta(D)\geqslant 0 . Equivalently, every such graph contains a Seymour vertex. Proof. For each integer n\leqslant 7 , all oriented graphs on the labeled vertex set \{1,\dots,n\} were generated. If D contains a vertex of outdegree zero, then D contains a Seymour vertex by Observation 3 ; hence such graphs require no further checking and were skipped during enumeration. For every remaining graph D , the values |N_{1}^{+}(v)| and |N_{2}^{+}(v)| were computed exactly for each vertex v , and the invariant \Delta(D)=\max_{v\in V(D)}\bigl(|N_{2}^{+}(v)|-|N_{1}^{+}(v)|\bigr) was evaluated. No graph with \Delta(D)<0 was encountered. ∎ Remark 5 . The verification for n=7 involves 3^{21}\approx 1.05\times 10^{10} labeled oriented graphs, of which more than 5.2\times 10^{9} satisfy the minimum outdegree condition. The computation completed in about 1 – 2 hours on a standard laptop (single CPU core, no GPU acceleration). For details on the computational aspects, please refer to App. A . 4 Split–Twin Extensions and Inductive Preservation In this section we introduce an inductive graph operation and show that it preserves the nonnegativity of the second neighborhood invariant. This yields infinite families of oriented graphs satisfying the second neighborhood property. 4.1 The split–twin extension Definition 6 (Split–Twin Extension) . Let D be an oriented graph and let x\in V(D) . A split–twin extension of D at x is the oriented graph D^{\prime} obtained as follows. The vertex x is removed and replaced by two new vertices x^{\prime} and x^{\prime\prime} , subject to the following rules: 1. For every vertex u\neq x , if u\to x is an edge of D , then both u\to x^{\prime} and u\to x^{\prime\prime} are edges of D^{\prime} . 2. The out-neighborhood N_{1}^{+}(x) is partitioned into two (possibly empty) sets A and B . 3. For each a\in A we add the

Read the complete text