Here are outline solutions for questions 1,2,7,9.
1 a) Take 2 disjoint paths of size |V|/2 and connect them by e.
b) For every (a,u) and (v,b) in E* add (a,b) to E* (if not already present).
2. This is exactly what Floyd Warshall computes if you fix the vertex order to be what is required by the question.
7. Let V(i,j,C) be the value of the game on numbers xi….xj when it is player c's turn. v(i,j,A) = -v(i,j,B). v(i,i,A)=xi. We want to compute v(1,n,A). v(i,j,A) = max(x_i +v(i+1,j,B), x_j+v(i,j-1, B)).
9. Run the party algorithm from the recitation on the line graph (see definition in ex.1 q.3) of T.