Fuente: Esta prueba está parafraseada de Foundations of Data Science, Hopcroft y Kannan, Ravi Kannan – Microsoft Research
Podemos demostrar que G está asintóticamente casi seguro conectado. Esto significa que la probabilidad va a 1 a medida que [matemática] n [/ matemática] aumenta. Seremos un poco más generales que una moneda justa y asumiremos que cada filo tiene una probabilidad [matemática] p [/ matemática] de estar presente.
Primero encontraremos un límite superior en el número esperado de componentes conectados de tamaño [math] k [/ math]. A menudo es más fácil trabajar en términos de expectativas que en términos de probabilidades, porque no tenemos que preocuparnos tanto por contar dos veces.
La probabilidad de que un vértice [matemático] k [/ matemático] dado forme un componente conectado es el producto de la probabilidad de que ningún vértice esté conectado a ningún vértice externo y la probabilidad de que los vértices estén conectados.
La primera probabilidad es [matemática] (1-p) ^ {k (nk)} [/ matemática] porque hay [matemática] k (nk) [/ matemática] bordes posibles entre los vértices [matemática] k [/ matemática] y el resto del gráfico, cada uno con probabilidad [matemática] (1-p) [/ matemática] de no ser elegido.
La segunda probabilidad es un poco más difícil, y es donde entra el límite superior. Si los vértices están conectados, existe un árbol de expansión, por lo que la probabilidad de que los vértices estén conectados es, como máximo, la suma de las probabilidades de que cada árbol de expansión esté presente. . Cada árbol de expansión tiene bordes [matemáticos] k-1 [/ matemáticos], por lo que una probabilidad [matemática] p ^ {k-1} [/ matemática] de estar presente. Se puede demostrar que hay [matemática] k ^ {k-2} [/ matemática] posibles árboles de expansión, por lo que el límite superior de la probabilidad es [matemática] k ^ {k-2} p ^ {k-1} [/matemáticas].
Entonces, la probabilidad de que un vértice [matemático] k [/ matemático] dado forme un componente conectado es como máximo [matemático] k ^ {k-2} p ^ {k-1} (1-p) ^ {k (nk) } [/ math], y hay [math] {n \ choose k} [/ math] conjuntos de vértices [math] k [/ math], por lo que un límite superior en el número esperado de componentes conectados de tamaño [math] k [/ math] es [math] {n \ choose k} k ^ {k-2} p ^ {k-1} (1-p) ^ {k (nk)} [/ math].
Ahora solo tenemos que considerar los componentes conectados de tamaño 1 a [math] \ frac {n} {2} [/ math], porque si hay un componente conectado de tamaño menor que [math] n [/ math] y más de [matemática] \ frac {n} {2} [/ matemática], debe haber un componente conectado de tamaño menor que [matemática] \ frac {n} {2} [/ matemática].
Si [math] p = \ frac {1} {2} [/ math], el número esperado de componentes de tamaño [math] k [/ math] es [math] {n \ choose k} \ frac {k ^ { k-2}} {2 ^ {kn -k ^ 2 + k -1}} [/ math]. Se puede demostrar que [matemáticas] {n \ elegir k} \ leq \ left (\ frac {en} {k} \ right) ^ k [/ math], por lo que podemos usar el límite superior más suelto [math] \ left (\ frac {en} {k} \ right) ^ k \ frac {k ^ {k-2}} {2 ^ {kn -k ^ 2 + k -1}} = \ frac {(en) ^ k} {k ^ 2 2 ^ {kn -k ^ 2 + k -1}} = \ left (\ frac {en} {2 ^ {n-k + 1}} \ right) ^ k \ frac {2} {k ^ 2} [/ matemáticas]. Ahora desde [math] k \ leq \ frac {n} {2} [/ math], [math] n-k + 1> \ frac {n} {2} [/ math]. Como el numerador crece linealmente y el denominador crece exponencialmente en [math] n [/ math], el número esperado de componentes conectados se reduce exponencialmente en [math] n [/ math]. Como el número de valores de [math] k [/ math] es lineal en [math] n [/ math], el número total esperado de componentes conectados de tamaño menor que [math] \ frac {n} {2} [/ matemática] disminuye exponencialmente, por lo que hay una alta probabilidad de que el gráfico esté conectado.
(Ver Hopcroft y Kannan para una prueba más detallada, especialmente cerca del final, y muchas otras ideas geniales).