The 'travelling salesman problem' is, for a given network of vertices connected by arcs of given lengths, to find the minimum distance that visits each vertex once and returns to the starting vertex.
For a small network, it is possible to find the minimum distance by examining every possible route, but as the size of the network grows, so does the number of routes that must be examined. It is helpful to find upper and lower bounds for the minimum distance.
The upper bound is easily found. We can construct the minimum spanning tree, using Prim's algorithm for example. The minimum spanning tree is the network of least length that connects every vertex. Each vertex can be visited by tracing forwards and backwards, in some order, each edge in the minimum spanning tree. The length of the path travelled is then twice the total length of the minimum spanning tree.
The minimum spanning tree is shown below.
It has length 11, so the upper bound for the travelling salesman problem for this network is 2*11=22.