I am looking for algorithms for the exact uniform sampling of connected simple graphs with $n$ vertices and $m$ edges. By "exact" I mean that every such graph should be generated with precisely (not approximately) the same probability.

If the density (i.e. $m$) is sufficiently high, then an Erdős-Rényi graph will be connected with relatively high probability. Thus we can generate such random graphs and reject any that are not connected.

I am looking for methods that will work down to $m=n-1$ (i.e. trees).

Any references to related literature would be most welcome.

I am looking for algorithms for the exact uniform sampling of connected labelled graphs with $n$ vertices and $m$ edges. By "exact" I mean that every such graph should be generated with precisely (not approximately) the same probability.

If the density (i.e. $m$) is sufficiently high, then an Erdős-Rényi graph will be connected with relatively high probability. Thus we can generate such random graphs and reject any that are not connected. If $m$ is small, this approach will require an impractically large number of trials before a connected graph will be found.

I am looking for methods that will work down to $m=n-1$ (i.e. trees).

Any references to related literature would be most welcome.