Sorry for vartical figures ,Top figure is HWQ#(i) and bottom one is HWQ3(ii)

3.Let G be a weighted graph with positive unique (no repetitions) edge weights, and let T1 be a MST of G. For example, if we start with the graph G shown in Fig HW2Q3(i), we will end up with the MST T1 shown in Fig HW2Q3(ii).

Suppose the path P = s, x1, x2, . . . , xk, t is the shortest path from s to t in T1. Is it always the case that P is also a shortest path from s to t in G? For instance, on the graphs above, the shortest path from a to b in T1 is a-c-b, which is also the shortest path from a to b in G. The question is whether this will be true no matter what graph we start with, or is it possible that in G there is a shorter path.

(a) Will a shortest path from s to t in T1 also always be the shortest path from s to t in G? 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 T1 will also be a shortest path in G.

(c) If you said NO, give a counterexample i.e. show

i. show the graphs G and the MST T1 in your counterexample

ii. state what are the vertices s and t in your counterexample

iii. show the shortest path from s to t in T1

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

6 CA 5 5 Fig HW2Q3(i) and Fig HW2Q3(i)