1. and 2. Write your own. Email me your answer if you think you want it verified. For 1., answer 'what' and 'how'. i.e. a possible point could be: "A lower bound is a ***** on a ***** such that ************". You fill in the blanks.

3. Prove len(t) >= weight(T*) + D[x1,y], for all tours t, where T* is a minimum spanning tree for full vertex set X and y is a nearest neighbour of x1 (ie. D[x1,y] <= D[x1,xi], for all xi neighbours of x1).

Let t be any valid tour visiting all cities, t = x1,x2,...,xn,x1. Recall that a tour is simply a spanning tree for all the cities when you remove one of the edges from the tour.

So let spanning tree T = (x2,x3),...,(xn-1,xn),(xn,x1) by not including the edge (x1,x2). Note that the spanning tree is a path. So our tour t = (x1,x2) + T and weight(T) = sum of weights of edges of T.

So, len(t) = len((x1,x2) + T) = D[x1,x2] + weight(T).

len(t) >= weight(T*) + D[x1,y]
D[x1,x2] + weight(T) >= weight(T*) + D[x1,y]

Suppose this isn't true. We know that weight(T) >= weight(T*), because T and T* are spanning trees of X and T* is a minimum weight spanning tree. So, if the statement isn't true, then D[x1,x2] must be less than D[x1,y]. But this is a contradiction because y is defined as a nearest neighbour of x1.

4. Let L1 be the 1-tree bound for D and let L be the bound defined in question 3. Prove that L <= L1.

Recall that a 1-tree lower bound is equal to the weight of a minimal spanning tree for all but one city x plus the weights of two edges adjacent to x.

Let x1 be the vertex(city) we leave out. So let T' be the MST for X-{x1}.

1-tree lower bound L1 = weight(T') + D[x1,u] + D[x1,v], where u and v are two vertices adjacent to x1 (u<>v).

Since L = weight(T*) + D[x1,y], where T* is an MST for X and y is a nearest neighbour of x1, we can rewrite the statement we are trying to prove.
L <= L1
weight(T*) + D[x1,y] <= weight(T') + D[x1,u] + D[x1,v]

T = T' + (x1,u) is a spanning tree for X, because T' is a spanning tree for X-{x1} and (x1,u) attaches x1 to T' to make a spanning tree for all X.
weight(T*) + D[x1,y] <= weight(T) + D[x1,v]

This is just like the proof for question 3. Suppose that this does not hold. We know that weight(T*) <= weight(T), because T* is an MST for X, and T is a (possibly mimimal, but not necessarily) spanning tree for X. Given that fact, for the statement not to hold, D[x1,v] must be less than D[x1,y]. This is a contradiction because y is defined as a nearest neighbour of x1, so the D[x1,v] cannot be smaller than the distance between x1 and its nearest neighbour y.