Number of graphs that almost contain a $k$-clique

Question

A (loop-free) graph almost contains a $k$-clique if it does not contain a $k$-clique, but adding an edge between any two different vertices that are not already connected by an edge would produce a $k$-clique.

To be more precise, these graphs satisfy the following properties:

1. The graph does not contain a $k$-clique.
2. For every two vertices $v,w$ not connected with an edge (such that $v\ne w$), there exists a set $S$ of $k-2$ vertices such that both $S\cup \{v\}$ and $S\cup \{w\}$ are cliques on $k-1$ vertices.

Is anything known about the number of pairwise non-isomorphic graphs satisfying these properties? Let's denote this number as $\#G(n, k)$, where $n$ denotes the number of vertices in the graph. Then does there exist $f(n)$ such that $\#G(n, f(n))$ is exponential or at least superpolynomial in $n$?

Answer 1

It is easy to see that for $k = 2$ the only graph almost containing $k$-clique is an empty graph $nK_1$. I don't have a proof, but I guess, that $\#G(n, 3)$ is exponential. Also the number $\#G(n, 3)$ is called the number of maximal triangle-free graphs and is computed up to $n = 24$ here. Computing the number of maximal triangle-free graph was suggested by Paul Erdős, but I've found only an upper bound here.

However I can easily and rigorously prove that $\#G(3k - 3, k)$ is exponential, i. e., $f(n) = \lfloor n / 3 \rfloor + 1$ is the function you are asking for.

Note that if graph $G$ is complete $(k - 1)$-partite with non-empty parts, then $G$ is almost containing $k$-clique. Indeed, by pigeon-hole principle among any $k$ vertices there are at least two from the same part, therefore at least one edge is missing. At the same time any two non-adjacent vertices belong to the same part. For each such pair we can select any vertex from each of other $k - 2$ parts. All this vertices except the initial pair are pairwise adjacent.

Let's add to a complete $(k - 1)$-partite graph $G$ with parts of size $2$ a $k - 1$-clique $H$. Then every vertex of $k - 2$ parts of $G$ should become adjacent to all but one vertices of $H$ such that every vertex of $H$ is adjacent to at least one vertex from every of these $k - 2$ parts. Adding missing edge for any such vertex of $G$ will give a $k$-clique. On the other hand adding an edge between any vertex of the remaining part of $G$ to a vertex of $H$ also would give a $k$-clique. Thus the resulting graph almost contains $k$-clique.

Note that if parts of $G$ have sizes $2$ then edge set between $G$ and $H$ can be selected in at least $$\frac{\binom{k - 1}{2}^{k - 2}}{(k - 1)!(k - 2)!} \sim \frac{(k - 1)^{k - 2}(k - 2)^{k - 2}}{2^{k - 2}} \cdot \frac{e^{k - 1}e^{k - 2}}{2\pi k (k - 1)^{k - 1}(k - 2)^{k - 2}} \sim \frac{e^{2k - 3}}{2^{k - 1}\pi k^2} = e^{k(2 - \ln 2) + o(k)}$$ ways. Here we select an unordered pair of distinct non-adjacent vertices of $H$ for every of $k - 2$ parts of $G$ and divide by the number of permutation of $k - 1$ vertices of $H$ and the number of permutations of $k - 2$ parts of $G$. So $\#G(3k - 3, k)$ is exponential.