**Answer to the first question:** 

 Please see the following figure for $n = 8$. All the red and black edges have weight $1$. The green edge $(C,H)$ has weight $2$. And, the blue edges have weight $0$. The edges that are not there have weight $\infty$; I have not drawn these edges for simplicity. 

Now, note that the cycle $(A,B,C,D,E,F,G,H)$ is the optimal tour with weight $5$. Also, the tour formed by the colored edges (red, green, and blue) has weight $6$.  Note that the tour formed by these colored edges is locally optimal to $\lceil n/2 \rceil$ change but it is not globally optimal.  

[![enter image description here][1]][1]

*Why colored tour is locally optimal?*

**Proof:** For the sake of contradiction assume that it is not locally optimal. It means that there exist at most four edges in the tour that can be replaced to obtain a smaller weight tour. Observe that to obtain a smaller weight tour, the edge $(C,H)$ must be replaced and the blue edges can not to be replaced. If you replace edge $(C,H)$, then you must add the edges $(C,B)$ and $(A,H)$; otherwise, the weight of the tour will become $\infty$. Now, there are two cases:

1. Add edges $(A,B)$. To complete the tour, you then must add the edges $(E,D)$ and $(F,G)$; otherwise, the weight of the tour will become $\infty$. But then, the number of edges added would be $5 \geq n/2$. Therefore, this set of operations is not allowed.

2. If you do not add edge $(A,B)$. Then, you must add edges $(B,E)$ and $(A,F)$. But then, to complete the tour, you must include edge $(D,G)$ of weight $\infty$. In that case, the cost of the tour will become $\infty$.

This proves that the tour formed by colored edges is locally optimal.


  [1]: https://i.sstatic.net/AiPEi.jpg