2. Independence is the key to a good research! (12 points) An independent set in a graph is defined as a set of
vertices with no edges connecting them, ie, no two of which are adjacent. Let G be a graph with ndl2 edges
(d > 1). Here, we c conduct the following probabilistic experiment for finding an independent set in G: delete each
vertex of G with all its incident edges independently with probability 1 - 1I /d.
【題組】
(a) [6 points) Compute the expected number of vertices and edges that remain after the deletion process.