pith. sign in

arxiv: 2606.30588 · v1 · pith:X4A26ZEXnew · submitted 2026-06-29 · 🧮 math.CO · cs.DM

A proof of Seymour's second neighborhood conjecture for oriented graphs with minimum out-degree equal to 7

Arpan Sadhukhan , R. B. Sandeep , Sagnik Sen This is my paper

Pith reviewed 2026-06-30 04:52 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords Seymour's conjecturesecond neighborhoodoriented graphsout-degreecomputer-assisted proofconstraint programming
0
0 comments X

The pith

Every oriented graph with minimum out-degree 7 satisfies Seymour's second neighborhood conjecture.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves Seymour's second neighborhood conjecture specifically for oriented graphs in which every vertex has out-degree at least 7. This extends the known range from the previous threshold of minimum out-degree 6, established in 2001. The argument first applies a sequence of local structural reductions to any supposed minimal counterexample and then uses a constraint-programming solver to confirm that the remaining finite obstruction models are impossible. A reader would care because each increment in the minimum-degree threshold narrows the gap toward a full resolution of the conjecture for arbitrary oriented graphs.

Core claim

We prove that every oriented graph with minimum out-degree 7 contains a vertex v satisfying |N^{++}(v)| >= |N^+(v)|. After exhaustive local reductions that shrink any minimal counterexample, the surviving obstruction models are shown to be infeasible by reproducible OR-Tools CP-SAT checks.

What carries the argument

A finite set of obstruction models obtained after a sequence of local reductions, verified for non-existence by CP-SAT infeasibility.

If this is right

  • The second-neighborhood property holds in every oriented graph whose smallest out-degree is 7.
  • The computer-assisted reduction-plus-solver pipeline eliminates all candidate counterexamples at this degree threshold.
  • The result raises the verified minimum-degree bound by one beyond the 2001 threshold of 6.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same reduction framework could be applied to minimum out-degree 8 if the new obstruction models remain manageable for the solver.
  • Success at degree 7 suggests that further incremental gains may be obtainable without a fully manual proof.
  • The approach may transfer to related questions on neighborhood ratios in other classes of directed graphs.

Load-bearing premise

Every possible minimal counterexample reduces through the listed local moves to one of the finite models that the solver checks.

What would settle it

An oriented graph with minimum out-degree 7 in which no vertex satisfies |N^{++}(v)| >= |N^+(v)|, or a counterexample that evades the listed reductions.

read the original abstract

We prove Seymour's second neighborhood conjecture on oriented graphs whose minimum out-degree is equal to $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$. 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript claims a proof of Seymour's second neighborhood conjecture for oriented graphs with minimum out-degree 7. It improves the 2001 threshold of Kaneko and Locke (degree 6) via a sequence of local reductions that reduce any minimal counterexample to a finite list of obstruction models, which are then shown infeasible by reproducible OR-Tools CP-SAT checks.

Significance. If correct, the result is a substantial advance in oriented graph theory, providing the first improvement on the out-degree threshold in two decades. The explicit use of reproducible solver checks for the finite cases is a methodological strength that supports independent verification.

major comments (2)
  1. [§3] §3 (Local reductions): the argument that the listed reduction rules are exhaustive for every possible minimal counterexample with δ⁺ ≥ 7 relies on case analysis whose completeness is not independently verifiable from the text; a single missed configuration would invalidate the reduction to the finite list.
  2. [§4] §4 (CP-SAT encoding): the description of the constraint model must explicitly confirm that the encoding enforces the oriented-graph condition (no bidirectional edges), the exact out-degree lower bound of 7 on every vertex, and the precise negation of the second-neighborhood property; any relaxation or omitted domain restriction would permit undetected feasible solutions.
minor comments (2)
  1. The reproducibility statement for the OR-Tools scripts should include the exact solver version, timeout settings, and seed values used in the reported runs.
  2. Notation for the second-neighborhood size N⁺(v) and the conjecture statement should be restated uniformly in the introduction and in the reduction sections to avoid minor inconsistencies.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive report. The comments highlight important points regarding verifiability of the reductions and explicitness of the solver encoding. We respond to each major comment below and indicate the revisions we will make.

read point-by-point responses

  1. Referee: [§3] §3 (Local reductions): the argument that the listed reduction rules are exhaustive for every possible minimal counterexample with δ⁺ ≥ 7 relies on case analysis whose completeness is not independently verifiable from the text; a single missed configuration would invalidate the reduction to the finite list.

    Authors: Section 3 derives the reduction rules by exhaustive examination of the possible local structures around any vertex v of out-degree at least 7 in a minimal counterexample. The cases are partitioned according to the size of the common out-neighborhood with N⁺(v) and the possible arcs between N⁺(v) and N⁺⁺(v). Each branch either produces an immediate reduction (contradicting minimality) or forces a configuration that is later ruled out by the computer check. While we maintain that the enumeration is complete, we accept that an explicit description of the partitioning criterion would aid independent verification. We will therefore insert a short paragraph at the beginning of §3 that states the systematic enumeration order (first by |N⁺(v) ∩ N⁺(w)| for w ∈ N⁺(v), then by the possible second-neighborhood arcs) and confirms that all 2^7 = 128 possible out-neighborhood subsets are accounted for by symmetry reduction. revision: partial

  2. Referee: [§4] §4 (CP-SAT encoding): the description of the constraint model must explicitly confirm that the encoding enforces the oriented-graph condition (no bidirectional edges), the exact out-degree lower bound of 7 on every vertex, and the precise negation of the second-neighborhood property; any relaxation or omitted domain restriction would permit undetected feasible solutions.

    Authors: The CP-SAT model in §4 is defined with binary variables x_uv for each ordered pair, the three families of constraints being (i) x_uv + x_vu ≤ 1 for every unordered pair, (ii) ∑_u x_vu ≥ 7 for every vertex v, and (iii) for every v the inequality |N⁺⁺(v)| < d⁺(v) expressed via auxiliary indicator variables for second-neighborhood membership. These are precisely the required conditions. Nevertheless, we agree that the current prose does not restate each property in a single sentence immediately before the constraint list. We will revise the opening paragraph of §4 to contain three explicit bullet points confirming that the model enforces the oriented-graph condition, the minimum out-degree of 7, and the negation of the second-neighborhood conjecture, thereby eliminating any possibility of misinterpretation. revision: yes

Circularity Check

0 steps flagged

Direct reduction proof with external solver checks; no circularity

full rationale

The derivation proceeds by explicit local reduction rules that are argued to exhaustively cover minimal counterexamples, followed by independent CP-SAT infeasibility checks on the resulting finite models. These steps are self-contained mathematical arguments plus reproducible external computation; they do not reduce any claimed result to a fitted parameter, self-citation chain, or definitional equivalence. Prior work cited (Kaneko-Locke 2001) is independent and non-overlapping. No load-bearing step matches any enumerated circularity pattern.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The proof relies on standard graph-theoretic axioms and the correctness of the OR-Tools solver; no free parameters or invented entities are introduced in the abstract.

axioms (1)
  • standard math Standard axioms of directed graph theory and the definition of oriented graphs (no 2-cycles).
    Invoked implicitly throughout the statement of the conjecture and reductions.

pith-pipeline@v0.9.1-grok · 5620 in / 1207 out tokens · 29611 ms · 2026-06-30T04:52:26.758936+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

19 extracted references · 6 canonical work pages · 1 internal anchor

  1. [1]

    N. Dean, B. J. Latka, Squaring the tournament—an open problem, Congressus Numerantium 109 (1995) 73–80

    1995

  2. [2]

    D. C. Fisher, Squaring a tournament: A proof of Dean’s conjecture, Journal of Graph Theory 23 (1996) 43–48

    1996

  3. [3]

    Havet, S

    F. Havet, S. Thomassé, Median orders of tournaments: A tool for the second neighborhood problem and Sumner’s conjecture, Journal of Graph Theory 35 (2000) 244–256

    2000

  4. [4]

    J. Ai, S. Gerke, G. Gutin, S. Wang, A. Yeo, Y. Zhou, On Seymour’s and Sullivan’s second neighbourhood conjectures, Journal of Graph Theory 105 (2024) 413–426. Sadhukhan et al. Page 22 of 23 Seymour second neighbourhood conjecture when𝛿= 7

    2024

  5. [5]

    Brantner, G

    J. Brantner, G. Brockman, B. Kay, E. Snively, Contributions to Seymour’s second neighborhood conjecture, Involve, a Journal of Mathematics 2 (2009) 387–395

    2009

  6. [6]

    Z. Cohn, A. Godbole, E. W. Harkness, Y. Zhang, The number of Seymour vertices in random tournaments and digraphs, Graphs and Combinatorics 32 (2016) 1805–1816

    2016

  7. [7]

    S.Dara,M.C.Francis,D.Jacob,N.Narayanan, Extendingsomeresultsonthesecondneighborhoodconjecture, DiscreteAppliedMathematics 311 (2022) 1–17

    2022

  8. [8]

    Espuny Díaz, A

    A. Espuny Díaz, A. Girão, B. Granet, G. Kronenberg, Seymour’s second neighbourhood conjecture: Random graphs and reductions, Random Structures & Algorithms (2024). To appear; arXiv:2403.02842

    work page arXiv 2024

  9. [9]

    Fidler, R

    D. Fidler, R. Yuster, Remarks on the second neighborhood problem, Journal of Graph Theory 55 (2007) 208–220

    2007

  10. [10]

    Ghazal, Seymour’s second neighborhood conjecture for tournaments missing a generalized star, Journal of Graph Theory 71 (2012) 89–94

    S. Ghazal, Seymour’s second neighborhood conjecture for tournaments missing a generalized star, Journal of Graph Theory 71 (2012) 89–94

    2012

  11. [11]

    C.Hernández-Cruz,H.Galeana-Sánchez, 𝑘-kernelsin 𝑘-transitiveand 𝑘-quasi-transitivedigraphs, DiscreteMathematics312(2012)2522–2530

    2012

  12. [12]

    Kaneko, S

    Y. Kaneko, S. C. Locke, The minimum degree approach for Paul Seymour’s distance 2 conjecture, Congressus Numerantium 148 (2001) 201–206

    2001

  13. [13]

    Liang, J.-M

    H. Liang, J.-M. Xu, On Seymour’s second neighborhood conjecture of𝑚-free digraphs, Discrete Mathematics 340 (2017) 1944–1949

    2017

  14. [14]

    Lim, A generalisation of Seymour’s second neighbourhood conjecture, 2020.arXiv:2001.07242

    J. Lim, A generalisation of Seymour’s second neighbourhood conjecture, 2020.arXiv:2001.07242

    work page arXiv 2020

  15. [15]

    Lladó, On the second neighborhood conjecture of Seymour for regular digraphs with almost optimal connectivity, European Journal of Combinatorics 34 (2013) 1406–1410

    A. Lladó, On the second neighborhood conjecture of Seymour for regular digraphs with almost optimal connectivity, European Journal of Combinatorics 34 (2013) 1406–1410

    2013

  16. [16]

    Mezher, M

    D. Mezher, M. Daamouch, A note on the second neighborhood problem for𝑘-anti-transitive and𝑚-free digraphs, 2024.arXiv:2405.17797

    work page arXiv 2024

  17. [17]

    Seymour's Second Neighborhood Conjecture for Subsets of Vertices

    T. Seacrest, Seymour’s second neighborhood conjecture for subsets of vertices, 2018.arXiv:1808.06293, version 3, 2019

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  18. [18]

    K. Guo, R. J. Kang, G. Zwaneveld, Seymour-tight orientations, 2026. URL:https://arxiv.org/abs/2603.29626. arXiv:2603.29626

    work page arXiv 2026

  19. [19]

    arXiv:2412.20234

    H.Huang,F.Peng,Animprovedboundonseymour’ssecondneighborhoodconjecture,2024.URL: https://arxiv.org/abs/2412.20234. arXiv:2412.20234. Sadhukhan et al. Page 23 of 23

    work page arXiv 2024