Finding a High Bound on Probability of Random Set first time user here.  English not my native language so I apologize in advance. Taking a final in a few weeks for a graph theory class and one of the sample problems is exactly the same as the $k$-edge problem.
We need prove that if each vertex selected with probability $\frac{1}{2}$, that the probability that except that we must find that the probability of the set being an
independent set is  $\geq (\frac{2}{3})^k$ (instead of $\frac{1}{2^k}$, like original problem).  
Here is what I am trying: I am looking into calculating the number of independent sets for each possible number of vertices $i$, for $i=0$ to $i=n$.  Once I calculate the probability of there being an independent set for the number of vertices $n$, I can take the expectation and union bound.
 A: I was the one who asked the original question that you linked to. Just for fun I tried to see if I could prove a better bound.  I was able to prove a bound even better than that. Here's a hint: you can use indicator variables and the second moment method.
A: You can adapt the answer of mjkxxxx to the mathstackexchange problem that you mentioned :
From each edge, you can choose one vertex. You get a collection of $K$ vertices with $K\leqslant k$ (because one same vertex can be choosen for different edges), say $v_1, \dots, v_K$. Each choosen vertex $v_i$ is linked by an edge to $k_i$ different vertices, with $k_i\geqslant 1$, and $\sum_{i=1}^{K} k_i=k $ (if the graph is simple).
Now, if , for any vertex $v_i$, either you don't select $v_i$, either you don't select any of the vertices linked to $v_i$, then you will get an independant set.
The probability of this event is greater than (and not equal, because some vertices can be linked to several $v_i$'s) :
$$ \prod_{i=1}^K \left(\frac12 +\frac12 (\frac12 )^{k_i}\right)$$
Then, using the convexity of the function $x\mapsto \log\left(\frac12 +(\frac12 )^{x+1} \right)$ and Jensen's inequality, the probability is greater than 
$$ \exp\left(K \log\left(\frac12 +(\frac12 )^{(\frac1K\sum k_i)+1} \right) \right) = \left(\frac12 +(\frac12 )^{\frac{k}{K}+1} \right)^K $$
Then posing $x=k/K$, the above formula can be written
$$ \left(\left(\frac12 + (\frac12 )^{x+1} \right)^{\frac1x}\right)^k $$
 and the function $x\mapsto \left(\frac12 + (\frac12 )^{x+1} \right)^{\frac1x}$ is increasing from $\frac34$ when  $x=1$ to $1$ when $x\rightarrow\infty$.
We conclude that the probability of picking an independent set is greater than $\left(\frac34\right)^k$. 
Remark 1 : This bound is optimal. When the graph is the union of couples of vertices linked by an edge, all the $k_i$' are equal to $1$, all the inequalities become equalities and the probability of picking an independent set is exactly $(3/4)^k$.
Remark 2 : If your graph was not simple, the probabilty would be greater than $(3/4)^{k'}$ where $k'$ is the number of useful edges.
