When is extra vertex required in arbitrage detection using Bellman Ford?

Question

I am studying applications of shortest path, in particular arbitrage.

Specifically, I was reading these two resources: https://stackoverflow.com/questions/2282427/interesting-problem-currency-arbitrage http://courses.csail.mit.edu/6.046/spring04/handouts/ps7sol.pdf

I do not understand when and why it is necessary to add an additional vertex to the graph in order to solve this problem.
In the solution outlined in here, halfway down page 7 it says "This method works because adding the new vertex ensures that all negative weight cycles are reachable..."

However, in most of the arbitrage problems I've seen, the graphs representing them are complete (fully-connected), so I cannot think of why this extra vertex is necessary.

When is it necessary to add this extra vertex and why? The best answer I can think of is when for some reason you cannot exchange a certain currency for another currency.

Answer 1

Yes there is no reason to add the extra vertex $v_0$ since the graph is fully connected and every vertex is reachable from every other vertex (the table specified in the problem seems to be a complete table). Since the graph is fully connected, if there is a negative weight cycle, we can find it by starting from any vertex. However, you would need the vertex $v_0$ if the graph was not fully connected so it is a more general answer.