Graphs and probabilities I was given the next question: 
Given that I have an infinite graph of the natural numbers as its vertices and the fact that for two vertices there is a probability of $0.5$ that they have an edge between them. I was asked to find the probability that the graph is connected (the graph is undirected).
My question is how do I approach this type of question? I tried looking at a smaller portion of a set of numbers yet I feel kind of lost. Any clues will be very helpful! I'd really like a clue instead of answering the question right away! Thank you very much.
 A: I cannot give you a proof or a hint, but a reference. As I noted in a comment, your construction yields with probability one the so called Rado graph (Yes, even if it seems to be a random process, it almost surely yields $-$ up to isomorphism $-$ only a single graph. Amazing, isn't it?).
Wikipedia states (somewhere in the linked section)

The Rado graph has diameter two [...]

and gives two references. This implies that it is connected (seemingly by lulu's initial reasoning). And this implies that your process yields a connected graph with probability one. I think this might help you to find an answer because now you at least know what you are looking for.

Further in this section of the Wikipedia article on your random graph model (it got the scary name Erdős–Rényi model), there is implied the following (warning: not completely rigorous):

Given a random graph $G_n$ on $n$ vertices and probability $p_n$ for any edge. If we have
  $$p_n>\frac{(1+\epsilon)\ln n}n,$$
  then in the limit $n\to\infty$ the random graph $G_n$ will be connected (with probability one).

Because $\ln n/n\to0$ for $n\to\infty$ but $p_n=1/2$, I take this as another hint that the Rado graph is connected. It seems you need quite some advanced mathematics to solve this problem rigorously.
