Probability of Selecting A Random Set in Graph with $k$ Edges That is Independent. 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!
 A: Choose an arbitrary node from each of the $k$ edges, thereby forming a set of $K \le k$ nodes.  If none of these nodes is selected, the set of selected nodes is independent, because it is missing at least one node from each edge.  The probability that none of the chosen nodes is selected is exactly $2^{-K} \ge 2^{-k}$.
A: Well, strictly speaking, this is only true for $k > 0$. For $k=0$ we have a graph with no edges, and the probability of picking an independent set is equal to $1=\frac{1}{2^0}$.
As for your approach, I didn't really understand what it is. If you consider any given selection of vertices, it is either independent or not. It is not a matter of probability, because the graph is not random. The graph is fixed, the selection is random.
Here is a possible way to approach this. For any fixed selection of vertices, the probability of picking this exact selection is $\frac{1}{2^n}$, where $n$ is the number of vertices in the graph. Here I use the assumption that we pick different vertices independently from each other. It is probably implied.
Now, from this observation we can see that the probability of picking an independent set of vertices is simply
$$
    p = \frac{m}{2^n},
$$
where $m$ the total number of different independent sets of vertices.
So, it comes down to proving that $m>2^{n-k}$. It isn't hard. Here is a hint that might help with that: you can use the fact that a graph with $n$ vertices and $k$ edges has at least $n-k$ connected components.
