In the Euclidean (metric) Traveling Salesperson Problem (TSP), we started with a DFS traversal of the minimum spanning tree (MST) and then skipped vertices that we had already visited. Why were we able to allow skipping of nodes? In the Euclidean metric, distance in measured in the number of edges, so removing edges makes the path shorter In a metric space the triangle inequality states that removing a vertex cannot lengthen the path It feels right Because DFS run on an MST adds an exponential number of vertices