Re: It is proved

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 $ G $ 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 $ C $, add many independent points $ X $, and add all the arcs from $ C $ to $ X $. Now the conjecture is true for this graph (one can take any of the sinks -- vertices in $ X $), but it is not true that one can choose a vertex of $ C $.

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.


Comments are limited to a maximum of 1000 characters.
More information about formatting options