Let a directed graph with a length-function . Furthermore assume that has a vertex with no incoming arrows, and for all there exists a path from to
Let be the length of the shortest path from to with at most arrows.
I've been asked to show: has a circuit with negative length for some
(the question doesn't say if it's for all n or not, but I assume that's what they mean).
I think that it's nonsense, since I think the following is a counterexample:
Let a circuit with negative value, and add
an arrow . Then we have a graph that has exactly all desired properties.
But now we have for all for all . But it's not true that for all ( for most we have ).
Can someone make this make sense to me? :P