We solved in polynomial time the densest subgraph problem. Namely finding a set U so that e(U)/|U| is maximum, namely the number of edges inside U over the size of U is maximum. Here we develop a fast approximation 1/2 for this problem. Say that we know the value of the optimum and it is . Consider the following algorithm:

(1) While: There is a vertex of degree strictly less than , remove the vertex and its edges from the graph and recompute the degrees (reduce the degree of its neighbors by 1).

(2) Return the resulting graph. Consider the optimum graph (of density ) OP T(V, E1)).

(a) Show that all degrees in OP T(V, E1) are at least

(b) Show that in the algorithm above, that removes vertices always contains OP T hence the graph does not turn empty.

(c) Show that the algorithm above is 1/2 approximation for the Densest-Subgraph problem