1. Show that, in the ATSP formulation, the connectivity constraints (6.61) and the subtour elimination constraints (6.62) are equivalent.

2. Show that the number of vertices of odd degree in a graph is even.

3. Let G = (V , A) be a complete directed graph such that |V | = 10 and the costs associated to the arcs belong to A, as reported in Table 6.51:

• check if the triangle inequality property holds for each arc cost;

• formulate the corresponding ATSP;

• solve the relaxed AP;

• determine a feasible ATSP solution and evaluate its quality;

• apply a 2-exchange procedure for finding a better feasible solution