Traveling salesman problem (TSP): what is the Relation with number of vertices and length of the found route? I know that there are many algorithms (exact or approximate) which implement the traveling salesman problem. I would like to know the relationship between the number of the vertices (i.e. the places to visit) and the length of the route found by these algorithms.

Intuitively, the fewer the vertices the shorter the route is. But can any one give me the mathematical relationship between the number of the vertices and the length of the route found by at least one of the existing traveling salesman algorithms?
Pick the hexagons that correspond to locations you want to visit. 

If these hexagons constitute a connected area (there is hexagon-path between any two), then the shortest solution is of length $c_1 \cdot n$ and the solution found by a good approximate algorithm is $c_2 \cdot n$ where $c_1$ and $c_2$ are some constants (i.e. they depend on the size of the hexagon).

If these hexagons are not connected, then the length of the best solution can be arbitrarily big: imagine three hexagons separated by $k$ spaces each, then the best path has length of $3\cdot (k+1) \cdot d_\text{hex}$, despite having only $3$ places to visit.

I hope this helps $\ddot\smile$
Well, since you're required to visit each city, and to visit it only once, the number of edges in your route exactly equals the number of vertices (assuming that you return to your original location at the end). The total length of the road is the sum over all these edges multiplied by their weights. It totally depends on the weights and has little to do with the number of vertices, if I understood your question correctly.