題組內容

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.

(b) I6 pointsI Based on Ca), ty to infer that for any graph with n vertices with nd/2 edges, there is an independent set with at least n/2d vertices.