A proof of Seymour’s second neighborhood conjecture for oriented graphs with minimum out-degree equal to 7 7
Arpan Sadhukhan, R. B. Sandeep, Sagnik Sen · 2026
Read A proof of Seymour’s second neighborhood conjecture for oriented graphs with minimum out-degree equal to 7 7 by Arpan Sadhukhan, R. B. Sandeep, Sagnik Sen (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-2606-30588.txt.
Introduction
Arpan Sadhukhan, R. B. Sandeep and Sagnik Sen prove a case of Seymour's second neighbourhood conjecture, a long-open problem about directed graphs. In an oriented graph, a vertex's second out-neighbourhood collects vertices reachable in exactly two steps but not one. The conjecture says some vertex always has a second neighbourhood at least as large as its first. Kaneko and Locke settled the conjecture in 2001 for graphs whose minimum out-degree is at most six.
Sadhukhan and his co-authors push that threshold to seven, the first improvement in two decades. Their proof is partly computer-assisted. A sequence of local reductions shrinks the problem to finitely many stubborn configurations. Those remaining cases are then eliminated by reproducible constraint-solver checks showing each one is impossible. The stronger result locates a Seymour vertex inside the closed neighbourhood of any minimum-degree vertex.
Catalog record
| CREATOR | Arpan Sadhukhan, R. B. Sandeep, Sagnik Sen |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 65 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.30588
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A proof of Seymour’s second neighborhood conjecture for oriented graphs with minimum out-degree equal to 7 7 Arpan Sadhukhan, R. B. Sandeep, Sagnik Sen Abstract We prove Seymour’s second neighborhood conjecture on oriented graphs whose minimum out-degree is equal to 7 7 . This gives, to our knowledge, the first improvement of the minimum out-degree threshold in two decades, since the work of Kaneko and Locke in 2001, who resolved the conjecture for oriented graphs whose minimum out-degree is at most 6 6 . The proof is partially computer-assisted: after a sequence of local reductions, the remaining finite obstruction models are eliminated by reproducible OR-Tools CP-SAT infeasibility checks. keywords Seymour second neighbourhood ,minimum out-degree 1 Introduction Let D be an oriented graph which denotes a finite directed simple graph without loops or digons; that is, there are no vertices u,v for which the arcs (u,v) and (v,u) are both included. For a vertex v\in V(D) , let N^{+}(v)=\{u\in V(D):vu\in E(D)\} denote the first out-neighbourhood of v , and N^{++}(v)=\{w\in V(D)\setminus N^{+}(v):\text{ there exists }u\in N^{+}(v)\text{ with }uw\in E(D)\} for the second out-neighbourhood of v . A vertex v is called a Seymour vertex if |N^{++}(v)|\geq|N^{+}(v)|. In the early 1990s, Seymour posed the now-celebrated second neighborhood conjecture: every oriented graph has a Seymour vertex. Seymour’s second neighbourhood conjecture was first published by Dean and Latka in connection with tournaments [ 5 ] . The tournament case, known as Dean’s conjecture, was proved by Fisher [ 8 ] ; Havet and Thomassé later gave a different proof using median orders [ 11 ] . The conjecture has since attracted substantial attention; see, for example, [ 1 , 2 , 3 , 4 , 6 , 7 , 9 , 12 , 14 , 15 , 16 , 17 , 18 , 19 , 10 , 13 ] . The conjecture has remained largely open and solved for very specific cases. In particular, Kaneko and Locke [ 14 ] proved the conjecture for every oriented graph with a vertex of out-degree at most 6 in 2001. This threshold remained unchanged since then. We improve the known minimum outdegree bound from 6 to 7 , proving the conjecture for every oriented graph with minimum out-degree at most 7 . In particular, we prove the following stronger version: Theorem 1.1 . Let D be an oriented graph with minimum out-degree less than or equal to 7 . Let s\in V(D) be any vertex of minimum out-degree. Then, there exists a seymour vertex in s\cup N^{+}(s)\cup N^{++}(s) . To the best of our knowledge, this result is the first improvement in more than two decades on the minimum-out-degree approach to Seymour’s Second Neighborhood Conjecture. The organization of the paper, together with a brief overview of the proof, is given in the preliminaries below. 2 Preliminaries Throughout, D is a finite simple oriented graph with first and second out-neighborhood as defined in the introduction. Let d^{+}(v)=|N^{+}(v)| denote the out-degree of v . We say that a vertex v out-dominates a vertex u if u\in N^{+}(v) . For a set X\subseteq V(D) , define N^{+}(X)=\bigcup_{x\in X}N^{+}(x). If a\in X,\;d_{X}^{+}(a) denote the number of out-neighbors of a in X . The out-distance from v to w denoted by d^{+}(v,w) is the length of a shortest directed path from v to w , if such a path exists. For vertex sets X,Y , define e(X,Y)=|\{(x,y)\in X\times Y:x\to y\}|,\;\;\text{where $x\to y$ denotes that $y$ is an out-neighbor of $x$}. If there is an arc (directed edge) from x to y , then x is denoted as the head and y is denoted as the tail of the arc. With slight abuse of notation, edges refers to arcs throughout the paper. In this paper, we denote by s a fixed vertex of minimum out-degree of the oriented graph D that we work with, with slight abuse of notation we denote d^{+}(s) by both \delta^{+}(D) and \delta . Definition 2.1 . We denote, A=N^{+}(s),\;B=N^{+}(A)\setminus A\;\text{and}\;C=N^{+}(B)\setminus(A\cup B). Then |A|=\delta , every vertex of A is at out-distance 1 from s , and every vertex of B is at out-distance 2 from s . Definition 2.2 . Let a_{1}\in A , denote a vertex of A such that |N^{+}(a_{1})\cap A| is minimum. If several vertices of A attain this minimum, break the tie by choosing one for which |N^{+}(a_{1})\cap B| is minimum. Definition 2.3 . Define, A_{1}=N^{+}(a_{1})\cap A,\;\text{and}\;A_{2}=N^{+}(A_{1})\cap(A\setminus A_{1}). For a vertex a\in A , all out-neighbours of a lie in A\cup B , thus, d^{+}(a_{1})=|N^{+}(a_{1})\cap A|+|N^{+}(a_{1})\cap B|=|A_{1}|+|N^{+}(a_{1})\cap B|. Now we will state two lemmas and a proposition that are already present in the paper [ 14 ] . We give the proofs in the appendix A for completeness. These two lemmas and the proposition will help us divide the problem into relevant cases. First, we state the general upper bound on the size of A_{1} with respect to the minimum out-degree of D . Lemma 2.4 . |A_{1}|\leq\left\lceil\frac{\delta}{2}\right\rceil-1. Proof. See Appendix A.1 ∎ We shall also use the following auxiliary fact, from the paper [ 14 ] which will be used often in the paper. Lemma 2.5 . Suppose that |A| is odd and |A_{1}|=\frac{|A|-1}{2}. Then D[A] is a regular tournament and |A_{2}|=|A_{1}|. Proof. See Appendix A.2 . ∎ Next we note the following proposition from [ 14 ] that shows existence of Seymour vertex under certain relaxed conditions. Proposition 2.6 . 1. If |B|\geq\delta , then s is a Seymour vertex. 2. If |B|\leq\left\lceil\frac{\delta}{2}\right\rceil and \delta\geq 2 , then a_{1} is a Seymour vertex. Proof. See Appendix A.3 . ∎ Outline of the paper In the rest of the paper we consider oriented graphs with minimum out-degree exactly equal to 7. Recall that s denotes a vertex with minimum out-degree. Thus if B\geq 7 then clearly s is a Seymour vertex. Also, by the above proposition if B\leq 4 , then a_{1} is a Seymour vertex. Thus in order to resolve Seymour’s conjecture for oriented graphs with minimum out-degree equal to 7, we only need to show the existence of a Seymour vertex in the following cases. 1. |A|=7,|B|=5 2. |A|=7,|B|=6 We divide the second case above into 3 sub-cases based on the size of A_{1} . By lemma 2.4 , we know |A_{1}|\leq 3 . Also, A_{1}\geq 1 , otherwise the minimum out-degree requirement of a_{1} is not satisfied when |B|=6 . Thus the only cases where we need to show the existence of a Seymour vertex are the following. 1. |A|=7,|B|=5 2. |A|=7,|B|=6,|A_{1}|=3 3. |A|=7,|B|=6,|A_{1}|=2 4. |A|=7,|B|=6,|A_{1}|=1 Each of the 4 cases above is handled in separate sections below. The proof of existence of a Seymour vertex in cases 1 and 2 are manual and requires no computer assistance, whereas the parts of the proof of existence of a Seymour vertex in cases 3 and 4 is computer assisted after effectively reducing the possibilities to a finite number of configurations based on certain assumptions. The rest of the paper following the overview of the proof is divided into four sections, with each section containing the proof of the existence of a Seymour vertex in each of the above mentioned cases and thus proving our claim. Overview of the proof The first