How to find Lower Bounds of Optimal Routes - TSP

A short tutorial on using minimum spanning trees to find lower bounds for optimal routes. This is part 2 of 3 in a series of tutorials on the Travelling Saleman Problem

[pingukang]

For IB students: The video states "loop" but we should interpret it as "cycle" instead.

[orva]

Konichiwagwan fam cheers for this vid!

[Raymaster]

Is there another method besides MST to get a lower bound value?
Thx for your help!

[tommy]

Will we ever not be told which vertex we need to delete, if so, how do we know which one to delete?

[stewarttrickett]

I presume that the node you delete is arbitrary. If you delete D, then you get an improved lower bound of 34.

[DiapaYY]

If the routes to A costed 100 each, that is not the cheapest.