The information needed to solve the tsp problem is not the distances matrix. It’s the set of Hamiltonian paths in your graph. And that scales factorially with the number of cities.
It is the subtour elimination (remove cycles) that makes the tsp problem difficult. Not the connectivity.
Which means that many of Hamiltonian paths are strictly dominated than others, so you don’t have to evaluate them at all. Same as in sorting you don’t have to evaluate all of the possible pairs.
I did not imply that all information is useful. I proposed that probably there is a lower bound of information that you definitely need to find the optimal solution to the tsp.
It is the subtour elimination (remove cycles) that makes the tsp problem difficult. Not the connectivity.