題組內容

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.