Construction aléatoire de graphe - Lycée Notre Dame du Grandchamp (Versailles)

On construit un graphe aléatoirement comme suit. On commence avec un seul sommet. À la première étape, on crée un autre sommet et une arête du premier sommet vers le second. À chaque étape qui suit :
• ou bien on crée une arête (non encore existante) d’un sommet existant vers un autre sommet existant ;
• ou bien on crée un nouveau sommet et une arête d’un sommet existant vers le nouveau sommet.
Peut-on obtenir des graphes connexes ? En combien d’étapes minimales peut-on obtenir un graphe connexe (de taille donnée) et avec quelle probabilité ? Quelle est la probabilité d’obtenir un graphe connexe (au bout de n étapes) ?