# Dynamic graph (?) - combination of connections between vertices that for each 3 exist min 1 edge

I have to find number of ways (combination) to create graph that for each 3 vertices there are minimum 2 vertices connected. There is n vertices. For example when n=3, there are 7 possible combinations. How can I make this with maybe dynamic programming?

• Try finding what graphs satisfying this condition look like. – Yuval Filmus Feb 10 '18 at 21:26
• Your graphs are the complements of triangle-free graphs. – Yuval Filmus Feb 11 '18 at 6:29

Your condition on the graph is the same as requiring its complement to be triangle-free. It is known that there are a lot of triangle-free graph. Indeed, since every bipartite graph is triangle-free, if we fix a partition of the vertex set into two sets of size $n/2$ (assuming for simplicity that $n$ is even), then we already get $2^{n^2/4}$ triangle-free graphs. It turns out that there aren't that much more, see this question on mathoverflow.