Dans l'énoncé de départ, si je comprend bien on demande un "graphe connexe aléatoire" où seul le nombre de noeuds est fixé.
Dans ce cas précis, on a de la chance: un "graphe aléatoire" et un "graphe connexe aléatoire" c'est presque la même chose, puisque un graphe aléatoire est presque toujours connexe.
Pour voir ça, d'abord, c'est quoi, un graphe aléatoire avec N sommets ? Si on veut un tirage equiprobable sur l'ensemble des graphes, il suffit de voir que chaque arête parmi les N(N-1)/2 possibles a exactement une chance sur deux d'exister: il y a autant de graphes avec cette arête que sans.
Donc pour tirer un graphe aléatoire avec N sommets, il suffit d'itérer parmi les N(N-1)/2 arêtes possibles et de les ajouter avec probabilité 1/2.

Une fois qu'on a fait ça, on a un graphe aléatoire. En pratique, si N n'est pas trop petit, il sera presque toujours connexe, car chaque sommet a en moyenne (N-1)/2 arêtes (c'est énorme!). Donc pour un algorithme efficace il suffit de tester si le graphe est connexe, et de tout recommencer à zéro s'il ne l'est pas. En pratique, ça marchera presque toujours du premier coup.
Bref. dès qu'on obtient un graphe connexe, on sait que c'est un graphe connexe tiré aléatoirement de manière uniforme parmi l'ensemble des graphes connexes de N sommets.

On a équiprobabilité. Le temps de calcul correspond à la taille du graphe, il est donc linéaire -- ou quadratique en N si on préfère, vu qu'il y a en moyenne N^2/2 arêtes à peu près. Et le nombre moyen d'étapes (puisqu'on recommence si le graphe n'est pas connexe) tend très vite vers 1 quand N tend vers l'infini. À partir de N=20 par exemple, on fait déjà moins de 1.2 étapes en moyenne.

Code source en C++:
Code C++ : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
 
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;
 
vector<vector<int> > aretes;
vector<bool> deja_vu;
 
void dfs(int v) {
  if (deja_vu[v]) return;
  deja_vu[v] = true;
  for (int i = 0; i < aretes[v].size(); ++i)
    dfs(aretes[v][i]);
}
 
int main() {
  int n;
  cout << "Nombre de sommets ? : ";
  cin >> n;
  bool tout_le_monde_est_vu = false;
  int nb_etapes = 0;
  do {
    ++nb_etapes;
    srandom(time(0) + nb_etapes * 1234567);
    // On tire chaque arete avec proba 1/2
    aretes.clear();
    aretes.resize(n, vector<int>());
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < i; ++j) {
        if (random() & 1) {  // une chance sur 2
          aretes[i].push_back(j);
          aretes[j].push_back(i);
        }
      }
    }
    // On teste la connexité avec un simple dfs.
    deja_vu.clear();
    deja_vu.resize(n, false);
    dfs(0);
    tout_le_monde_est_vu = true;
    for (int i = 0; i < n; ++i) {
      tout_le_monde_est_vu &= deja_vu[i];
    }
  } while(!tout_le_monde_est_vu);
  cerr << "Trouve! en " << nb_etapes << " etape(s). " << endl;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < aretes[i].size(); ++j) {
      if (i < aretes[i][j]) {
        cout << i << " " << aretes[i][j] << endl;
      }
    }
  }
  return 0;
}

Edit: merci pour les balises :-)