Graph generation given number of edges and nodes

This is what I think you requested, but probably not quite what you want. It gives all graphs without regard to isomorphism, hence the number grows quickly.

toEdgePair[m_] := 
 With[{j = Floor[(-1 + Sqrt[1/2 + 8*m])/2] + 1}, 
  UndirectedEdge[m - (j^2 - j)/2, j + 1]]

allGraphs[v_, e_] := Module[
  {edges = Subsets[Range[Binomial[v, 2]], {e}]},
  edges = Map[toEdgePair[#] &, edges, {2}];
  Map[Graph[#, VertexLabels -> "Name"] &, edges]
  ]

If you prefer long 1-liners...

allGraphs2[v_, e_] :=
 Map[Graph[#, VertexLabels -> "Name"] &, 
  Map[toEdgePair[#] &, Subsets[Range[Binomial[v, 2]], {e}], {2}]]

Here is an example. It gives an idea of what I mean about getting large due to inability to weed out isomorphic "repeats". One could of course do that after the fact. I do not know offhand how to generate efficiently so that there are no such repeats. A somewhat inefficient method in terms of time, but reasonable in memory, would be to generate iteratively. Then check each new graph against all prior retained ones, and discard if it is isomorphic to any of those priors.

allGraphs[5, 6]

This information is already available - why not just Import it? Brendan McCay lists all graphs up to order 10 (as well as special types of graph to higher order) here: http://cs.anu.edu.au/~bdm/data/graphs.html

Comparing the numbers against that page, we find that GraphData already lists all graphs up to order 7. Thus, for example, you can list all graphs of order 5 as follows:

graphNames = GraphData[5];
Grid[Partition[Table[
  Labeled[GraphData[name], name],
  {name, graphNames}], 5, 5, {1, 1}, ""],
ItemSize -> 10, Dividers -> All]

Beyond order 7, GraphData is incomplete. Brendand McCay's page lists all graphs up to and including order 10 in Graph 6 format, which Mathematica can import. For example, you can grab all four graphs of order 3 this easily:

Grid[Partition[
  Import["http://cs.anu.edu.au/people/bdm/data/graph3.g6", "GraphList"], 2],
  Dividers -> All, Spacings -> {3, 3}]

The files get very large, though, so it might make sense to import them as text and grab what you need. For example, here are the last 6 of the 12346 graphs of order 8.

strings = StringSplit[
  Import["http://cs.anu.edu.au/people/bdm/data/graph8.g6", "Text"]];
strings // Length
Grid[Partition[
  Table[ImportString[s, "Graph6"], {s, strings[[-6 ;;]]}],3], 
  Dividers -> All, Spacings -> {3, 3}]

Given that there are 12005168 graphs of order 10 and 1018997864 of order 11, I think you are unlikely to improve on this using IsomorphicGraphQ.

Update 2: Below, I used Union[..., SameTest -> IsomorphicGraphQ]. This is slow (quadratic in the number of graphs). The performant way to do it is DeleteDuplicatesBy[..., CanonicalGraph].

---

Update: It turns out Combinatorica has a function for this, called ListGraphs. You can enumerate all graphs with 6 edges and 5 vertices using

<<Combinatorica`

ListGraphs[6, 5]

GraphPlot /@ %

This will return all possible non-isomorphic graphs, not only the connected ones. How the function works is described in detail in the book Computational Discrete Mathematics.

However, the book itself mentions that enumerating these graphs is a computationally difficult problem, and recommends using precomputed tables (see Mark McClure's answer).

Unfortunately loading Combinatorica issues a warning since version 8 of Mathematica but as of version 9 there are still lots of useful functions in Combinatorica that are missing from core Mathematics. Also, the book I mentioned is a nice guide to the implementation of the functions and the theory behind them.

---

Here's an alternative to Daniel's solution. The advantage is that it weeds out more equivalent graphs at the first step, so you should be able to go to higher numbers. Sorry about the messy code.

(* e edges, n vertices *)
gengraphs[e_, n_] /; e <= (n (n - 1))/2 :=
 tri[n] /@ Permutations@PadRight[ConstantArray[1, e], (n (n - 1))/2]

(* this arranges elements of a list into an n by n symmetric matrix
   hacked together from code by @Mr.Wizard *)
tri[n_][elems_] := 
 With[{m = 
    Take[FoldList[RotateLeft, elems, Range[0, n - 2]], All, n]~ LowerTriangularize~ -1}, m + Transpose[m]]

Now we can weed out graphs that are not connected and those which are isomorphic with each other. For example, for 6 edges and 5 nodes,

Select[Union[AdjacencyGraph /@ gengraphs[6, 5], SameTest -> IsomorphicGraphQ], ConnectedGraphQ]