1. L is coNPc <=> L is in coNP and for all A in coNP, A<= p L <=> 
   \bar{L} is in NP and for all B in NP, B <= p \bar{L} <=> \bar{L} is NPc
  the only thing that requires an explanatin abouve is 
    for all A in coNP, A<= p L <=> for all B in NP, b <= p \bar{L}
This is true since (i) going over all A in coNP is the same as going over all
\bar{A} = B in NP, and (ii) A <= p L <=> \bar{A} <= \bar{L}

2. by 1 we can show that \bar{tautology} is NPc. 
\bar{tautology} = {phi | phi is falsified by some truth assignment}
Now the reduction 
     phi -> not (phi) 
is a polytime reduction from  SAT to \bar{tautology} (can you see why?)
This shows that \bar{tautology} is NP-hard. Also \bar{tautology} is clearly in 
NP (the witness is a falsifying assignmnet), and so \bar{tautology} is NPc 
which makes tautology coNP complete.

3. We first check that the graph has a k-clique (remember, we assume that we 
have a polytime algorithm with that); if it doesn't return NULL.
Otherwise, we remove edges one by one as long as a k-clique still exists 
in the remaining graph (again, apply the polytime alg for that).

At the end we remain with a set F of surviving efges. We claim that F is
precisely all possible edges between a certain subset of k vertices. Why? 
clearly, F contain a k-clique. Suppose it contains more than that, then 
consider an edge e in F sych that F-e contains a k-clique. Then this e should
have been removed by the algorithm: when it was considered for removal, the clique in F-e existed in the graph, and hence 
e should have been removed. Contradiction.

To sum up, as output the algorithm needs to give the list of vertices which still have some edges (notice that the analysis above
implies that there will be k such vertices and that these vertices will form a clique).

4. The problem as stated is not quite right (apologies!). What we actually need to show that MAX-SAT is self reducible 
with respect to COUNT-SAT, where COUNT-SAT = {<phi,k> | phi is a CNF formula so that at least k of its clauses can be satisfied}. 
So suppose we have a polytime algorithm for COUNT-SAT then we can solve MAX-SAT polynomially. 
We first show how to solve the search version of SAT-COUNT, namely, to find a truth assignment tha satisfies at least k clauses.
A predlude: Given phi, let's consider the formula phi_1 which is the same as phi except we set x_1 to FALSE, and let phi_T be the 
same as phi except we set set x_1 to F. If by doing so we satisfied a cluase we will keep track of that. If we get clauses 
which are false we simply delete them. For example

 phi = x1 V x2  ,  ~x1, x2 V ~ x3
then phi_F = x2, T,  x2 V ~x3
     phi_T   T ,, x2 V ~x3

We first check if phi,k is a YES instance. If not, as usual, we return NULL.
Now, we effectively want to check whether it is a "good idea" to set x_1 to F or to T. If phi_F is a formula so that k' of 
its clauses can be satisfied, where k' is k - the clauses that got satisfied when we substituted x1 with F, then we can 
go on with this assignment. Otherwise we will set x1 to T. We continue this way with x2, x3 etc. The invariant is that we 
always make it possible to extend the truth assignment we have to one that satisfies at least k clauses.

Onc we solved the search problem we simply do a binary search to look for the biggest possible k. (n fact for 
polynomiality a linear search is good as well.)