No puedo darle una prueba o una pista, sino una referencia. Como señalé en un comentario, su construcción rinde con probabilidad uno el llamado Gráfico de Rado (Sí, aunque parezca un proceso aleatorio, es casi seguro que se produzca $-$ hasta el isomorfismo $-$ sólo un solo gráfico. Increíble, ¿verdad?).
Wikipedia estados (en algún lugar de la sección de enlaces)
La gráfica de Rado tiene un diámetro de dos [...]
y da dos referencias. Esto implica que está conectado (aparentemente por el razonamiento inicial de lulu). Y esto implica que su proceso produce un gráfico conectado con probabilidad uno. Creo que esto puede ayudarte a encontrar una respuesta porque ahora al menos sabes lo que estás buscando.
Más en este sección del artículo de Wikipedia sobre su modelo de grafos aleatorios (obtuvo el espantoso nombre Modelo de Erdős-Rényi ), está implícito lo siguiente (aviso: no es completamente riguroso):
Dado un gráfico aleatorio $G_n$ en $n$ vértices y probabilidad $p_n$ para cualquier borde. Si tenemos $$p_n>\frac{(1+\epsilon)\ln n}n,$$ entonces en el límite $n\to\infty$ el gráfico aleatorio $G_n$ se conectará (con probabilidad uno).
Porque $\ln n/n\to0$ para $n\to\infty$ pero $p_n=1/2$ Me lo tomo como otro indicio de que el gráfico de Rado está conectado. Parece que se necesitan unas matemáticas bastante avanzadas para resolver este problema con rigor.
