Undergraduate. Proof based. Take note that the converse is definitely not true. But if we assume cycle exists in the predecessor graph, then there has to be a negative cycle cost directed cycle on the original graph.

Key: Page 137, last 10 lines and keep reading. The invariant of the label correcting algorithm is the key.

The reduce costs of all arcs \((i, j)\) on the predecessor graph have to have a reduced cost that is less than zero.\(\forall (j, pred(j)): d(j) \ge d(i) + c_{i, j}\).