The other day, I needed to create a graph with $10$ vertices, $16$ edges, and which didn't have a loop of four vertices, $C_4$, or a daisy-chain of three $3$-cliques (see picture) as sub-graphs. Turns out there is one such graph up to isomorphism (two butterfly sub-graphs with four edges spanning between them). And any graph on $10$ vertices with $17$ or more edges will contain a copy of $C_4$ or a daisy-chain of three $3$ cliques. So the one graph I found is the unique maximally edged (proper term?) graph that avoids the previously mentioned sub-graphs.
Now I want to do a similar search. I want to find all graphs (up to isomorphism) with $11$ vertices that have as many edges as possible and avoid the three graphs in the picture below. I wrote a python program to solve this question on $10$ vertices; but it's slow and unsophisticated so it won't scale well and I'm hoping for a better solution.
This problem comes up when solving a question I learned from Neil Sloane on Numberphile: given $n$ distinct integers, how many of their pair-wise sums can be powers of two? Turns out that if you treat the $n$ integers as vertices in a graph and add an edge between any two whose sum is a power of two, then such graphs must avoid the three sub-graphs in the picture below. For instance, with this graph generation approach, we can solve the case for $n=10$ integers/vertices proving that at most $15$ of their pair-wise sums can powers of two (see question/answer here). I'm hoping to write some math software that automates the tedious parts of this approach to find the optimal solutions (if everything goes well) to $n\le 50$.
In general then, I'm wondering: given a set of sub-graphs, how does one efficiently construct all graphs (up to isomorphism) that have as many edges as possible and avoid those sub-graphs? I figure the time-complexity here might be exponential in the number of vertices. But if $10$ vertices is solvable, I'd like to know what else is in reach.
My only optimization for the $10$ vertex case was to assume that any solution would have at least one $3$-clique. So my program, which brute-force built up all possible graphs edge by edge, checking for bad sub-graphs as it went, started with a $3$-clique to cut down the search space. I didn't check for graph isomorphisms while doing the construction; just when printing out solutions so there's likly a lot of time savings there.
