Open Problem Garden - Seymour's Second Neighbourhood Conjecture - Comments

Counterexample for the proof (re: Seymour's Second Neighbourhood Conjecture)

sjcjoosten — Fri, 18 Mar 2011 11:34:26 +0100

As was indicated, Lemma 2 is false. Here is a counterexample to lemma 2. Note that it is not a counterexample to the conjecture, since it has two sinks.

Re: So is this proof valid or (re: Seymour's Second Neighbourhood Conjecture)

rs — Sun, 08 Aug 2010 00:21:02 +0200

I believe the mentioned prof is not valid. Is your proof working? And sorry for the late reply, our system falsely recognized your comment as a spam.

So is this proof valid or (re: Seymour's Second Neighbourhood Conjecture)

Anonymous — Sun, 14 Mar 2010 07:02:52 +0100

So is this proof valid or not? I am currently working on a proof and am wondering whether or not I should be bothering

Re: It is proved (re: Seymour's Second Neighbourhood Conjecture)

Robert Samal — Sat, 12 Dec 2009 22:37:34 +0100

Thanks for the reference. The proof, however, seems flawed. The basic outline of the proof (if I understood it correctly) is as follows:

\item If has a sink, then this sink satisfies the conditions. \item An oriented graph without directed cycles has a sink. \item Then one proves directly that a graph containing a directed cycle has a vertex (even on that cycle) that satisfies the conditions.

The last part (Lemma 2 of the manuscript), is not true -- take a directed cycle , add many independent points , and add all the arcs from to . Now the conjecture is true for this graph (one can take any of the sinks -- vertices in ), but it is not true that one can choose a vertex of .

The omission in the proof of Lemma 2 is that it's tacitly assumed, that adjacent vertices of the cycle have no common out-neighbours.

It is proved (re: Seymour's Second Neighbourhood Conjecture)

Anonymous — Sat, 12 Dec 2009 14:39:09 +0100

This conjecture has been proved. You can find the proof here .

Seymour's Second Neighbourhood Conjecture

nkorppi — Tue, 09 Oct 2007 19:43:47 +0200

Author(s): Seymour

Subject: Graph Theory » Directed Graphs

Conjecture Any oriented graph has a vertex whose outdegree is at most its second outdegree.