Seymour's Second Neighborhood Conjecture

Notations & definitions
The open problem
Incorrect proofs
Special cases
Correct(?) proofs
Related problems
Other results
About this website

About this website

This website explores a hitherto unsolved problem in graph theory: Seymour's Second Neighborhood Conjecture (SSNC). I encountered this open problem for the first time on a website of Nate Dean, Texas Southern University, which presents a list of open problems in graph theory. The problem was originally brought up by Paul Seymour around 1980 (although, according to some sources, Seymour formulated the conjecture in 1993).

The abovementioned website was last updated in May 2007. Therefore, I cannot guarantee that Seymour's Second Neighborhood Conjecture still has not been solved yet. However, in an e-mail correspondence Paul Seymour himself told me that, and I quote, "there have been several 'proofs', but they are all wrong." An overview of these incorrect proofs, as found on the Internet, is given on this website. You can find these erroneous proofs, including a brief summary of each proof and its mistake(s), here.

As you will notice, this website also includes a page entitled "Correct(?) proofs". This does not mean that a correct proof of Seymour's Second Neighborhood Conjecture actually exists, but just that I was unable to find the article containing the proof. Nevertheless, in all likelihood this proof is also incorrect.

About the creator of this website

This website was made by me, Tim Verheijen, as a project for the course Advanced Graph Theory, given by Dr Wieb Bosma at the Radboud University Nijmegen, the Netherlands. At this university, I have been studying Mathematics for five years now. Next year, I would like to get my teaching qualification, which will enable me to teach mathematics in secondary school.

If you have any questions, remarks, or comments about this website, please contact me at timverheijen[at]student[dot]ru[dot]nl.

Final remark

Although the correct spelling of the English word "neighbour(hood)" is with a "u", I used the American version "Seymour's Second Neighborhood Conjecture", since Paul Seymour is an American mathematician – see it as a small tribute. However, if I used the word "neighbour(hood)" in another context, I adhered to the British English spelling conventions.

Back to top