Run the Nearest Neighbor and MST algorithm on the following graph to find a Hamiltonian cycle

started from Boston. For clarity, only needed edges are shown.

$1.$ Show the cycle generated by the Nearest Neighbor algorithm

$2.$ Display the resulting Minimum Spanning Tree $($MST$)$ and the Hamiltonian cycle generated by

the MST algorithm. For the Prim$$s algorithm subroutine, initiate your cloud at Boston. When

illustrating your tree, ensure that within each level of the tree, the order of the nodes from

left to right corresponds to the sequence in which they were added to the cloud during Prim$$s

algorithm.

$3.$ Given your result from $2,$ provide a lower bound on the optimal solution to TSP on the graph