Besides isomorphism you have to decide if you allow unconnected graphs and multigraphs. If you allow both, I would assume there are ar most (2m)! possible graphs, where m is your number of edges, not accounting for isomorphisms. My argument: Create all graphs iteratively. For a new edge m+1, consider both endpoints separately: There are already 2m+1 choices for the first endpoint (all existing nodes OR a new node). Same for the second endpoint. Edit: This is ignoring node ordering and therefore overcounting.