7
$\begingroup$

In a graph with $k$ edges, if we pick every vertex randomly and independently with a probability of $\frac{1}{2}$, prove that the probability that this set of randomly chosen vertices is an independent set is greater than $\frac{1}{2^k}$.

The approach I am using involves considering all possible selections of vertices, and bounding the probability that those selections have an independent set.

Thanks so much!

  • 0
    What do you mean by independent set ?2012-11-20
  • 0
    @saposcat An independent set in a graph is a subcollection of the vertices such that the induced subgraph has no edges.2012-11-20

2 Answers 2