I have been given a question and I dont even know where I should begin:
Given a graph with $n$ nodes where every node has at least $\sqrt{n}$ neighbors,
We build the set $S$ in the following order: for $0.3n$ times we pick each time one node randomly and independently and put it in $S$ (repeatition is possible).
Find a low bound for the probability that for every node in the graph there is at least one neighbor in $S$.
Assume that $n$ is a big number.
I have tried all sort of things but I can't seem to get close to the solution, I thought to use indicators to try and sum the number of different nodes in $S$ and by using the Central limit theorem (n is a big number) to somehow get the answer, but when I started defining the indicators it got messy and I could not define them.
P.s . The way $S$ is built reminded me of a Binomial distribution but i failed there too.
I would appreciate if someone could give me the solution.
Let $I_v$ be the indicator of the event that $v$ has no neighbors in $S$. Then $$E(I_v) \le (1-\sqrt{n}/n)^{3n/10} \le \exp(-3\sqrt{n}/10)\,,$$ since $1-x \le \exp(-x).$ Summing over all vertices in the graph, we find that the probability there is a vertex with no neighbor in $S$ is at most $$E (\sum_v I_v) \le n\exp(-3\sqrt{n}/10)\,.$$ Thus the probability that for every node in the graph there is at least one neighbor in $S$ is at least $1-n\exp(-3\sqrt{n}/10)\,.$