[Independent Set] There is an undirected graph G=(V={v1,,vn},E). There are a total of n ! possible orderings of these vertices. Pick one such ordering uniformly at random =(1,,n). Then consider the following process: Begin with S=. Then, at each step (for i=1 to n ), if for all uS,(u,vi)/E, add vi to S. Denote by d the maximum degree of a vertex of V. Prove that the proposed algorithm achieves an independent set with expected value of at least 1/d fraction of the optimal solution