As Daniel pointed out you should not have much problem tricking the default RandomGraph
with a While
type loop. However the problem you may face is when the number of vertices and edges are close compared to their absolute value. For large number of vertex and fixed edges of same order the above method fails. Also the timing will be pretty unpredictable for a given vertex-count and edge-count. For such case you can use the following algorithm.
select[sub_Graph] := Module[{found, ed, sel, val},
found = {};
ed = EdgeList[sub];
While[Length@found == 0,
If[TreeGraphQ[sub] === True, sel = 0;
val = RandomChoice@VertexList[sub]; Break[]];
sel = RandomChoice[ed];
If[EdgeConnectivity[EdgeDelete[sub, sel]] === 0,
ed = DeleteCases[ed, sel], AppendTo[found, sel];
val = RandomChoice@Flatten@(List @@@ found)]
];
{val, If[sel === 0, sub, EdgeDelete[sub, sel]]}
];
combine[g1_Graph, g2_Graph] := Module[{edge, graphs},
{edge, graphs} = Transpose[select /@ {g1, g2}];
EdgeAdd[GraphUnion @@ graphs, UndirectedEdge @@ (edge)]];
nRandomGraph[{vertex_Integer, edge_Integer}] /; edge >= vertex - 1 :=
Module[{comps, list, g},
g = RandomGraph[{vertex, edge}];
If[GraphQ[g] === True,
comps = ConnectedComponents[g];
list = Subgraph[g, #] & /@ comps;
Fold[combine[#1, #2] &, First@list, Rest@list]
]
];
Testing the above function to generate $100$ graphs with fixed edge and vertex count.
While loop:
n = 100;
list = {};
While[Length@list =!= n,g = RandomGraph[{57, 66}];
If[ConnectedGraphQ[g] == True,AppendTo[list, g]]]; // AbsoluteTiming
{18.411692, Null}

Above algo:
mList = Table[nRandomGraph[{57, 66}], {n}]; // AbsoluteTiming
{2.828562, Null}

A bigger example where the While
method kept on running for ever...
nRandomGraph[{557, 900}]; // AbsoluteTiming
{17.551914, Null}
Now lets look at the vertex degree distribution of both lists of generated graphs.
pdfs = Module[{data = VertexDegree [#]},
smD = SmoothKernelDistribution[data]; PDF[smD, x]] &;
smdis = pdfs /@ mList;
smdisW = pdfs /@ list;

In the above we are plotting those distribution together along with their respective mean in rainbow colors. The solid lines are for graphs that the above algorithm generates. The lines with opacity are using While
and RandomGraph
functionality of Mathematica. Hope this gets you going!
Bias:
You can see the bias of above algorithm compared to Mathematica default RandomGraph
. We draw the default pdf in dark red line. For the above algorithm $5000$ graph sample was taken and the distribution was estimated. This pdf is the thick line.
uniDis[n_, m_] := GraphPropertyDistribution[VertexDegree[g, v],
g \[Distributed] UniformGraphDistribution[n, m]];
pdfs = Module[{data = VertexDegree[#], smD},
smD = SmoothKernelDistribution[data]; PDF[smD, x]] &;
smdis = pdfs /@ mList;
Plot[Evaluate@{PDF[uniDis[57, 66], x], Mean@smdis}, {x, 0,10}, PlotRange -> All,
PlotStyle -> {{Thick, Darker@Red}, {Thickness@.01,Directive[Red, Opacity[.4]]}}
,Filling -> {1 -> {2}},FillingStyle -> LightOrange, Axes -> None, Frame -> True]
