Revision history [back]

You could try the following

E=Set(G.edges())
V=G.vertices()
for s in E.subsets():
    H=Graph()
    H.add_edges( s )
    #If you are interested only in spanning subgraphs you have to include this line
    H.add_vertices( V )
    if check( H ):
        graphs_you_want.append( H.graph6_string() )

One thing to keep in mind is that you might want to get the canonical label of H into the list of graphs you want (in case you are interested in non labelled subgraphs). This could help avoid duplicates (isomorphic graphs) in the list.

This does not guarantee it will be faster, it will take the same time (maybe more) as your first approach when G is the complete graph.