Let G be a weighted graph with positive unique (no repetitions) edge weights, and let G0 be the the graph which has exactly the same vertices and edges as G, except that for every edge (u, v) in G0 , weight(u, v) in G0 = weight(u, v) in G +4. For example, if we start with the graph G shown in Fig HW2Q3(i), we will end up with the graph G0 shown in Fig HW2Q3(ii). Suppose the path P = s, x1, x2, . . . , xk, t is the shortest path from s to t in G. Is it always the case that P is also a shortest path from s to t in G0 ? For instance, on the graphs above, the shortest path from 1 to 2 in G is 1-3-2, which is also the shortest path from 1 to 2 in G0 . The question is whether this will be true no matter what graph we start with.

(a) Give a YES/NO answer to the above question.

(b) If you said YES, give a brief explanation i.e. explain why a shortest path in G will always also be a shortest path in G0 . If you said NO, give a counterexample i.e.

show the graphs G and G0 in your counterexample

state what are the vertices s and t in your counterexample

calculate the shortest path from s to t in G

show that this path is not the shortest path from s to t in G0 by finding another path from s to t in G0 which is shorter.