For each of the following parts, state True or False. If true, give a short proof. If false, give a

counterexample:

(1). Using Kruskals algorithm, edges are (always) inserted into the MST in the same order as using Prims

algorithm.

(2). If an edge e is part of a TSP tour found by the quick TSP method then it must also be part of the

optimal TSP tour.

(3). If an edge e is part of a Shortest Path Tree rooted at A then it must also be part of a Shortest Path

Tree rooted at B.

(4). If all edge costs are increased by 2 the Shortest Path Tree rooted at A remains the same tree.

(5). An edge e whose cost is the largest in the graph can not be part of a Minimum Spanning Tree