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

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$$?

• Just some clarifications: 1) You probably want your pairwise non-isomorphic graphs to have the same number of vertices; otherwise, it would not be interesting! 2) Do you want to construct a set of such graphs where each pair satisfies your requirements or simply want to know how many such pairs can be possible? Commented May 13 at 7:52
• @codeR 1) Yes, exactly $n$ vertices. 2) A construction of such a set (for every $(n,k)$) would be interesting. I am not as much interested in pairs per se, but rather just don't want to count isomorphic graphs as different. Though, I suppose, it only is a factor of exactly $n!$. Commented May 13 at 9:07

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.
• The proof appears much shorter than I expected! But I suppose determining asymptotics of the size of the smallest $k$-clique-free graph that contains all $k$-clique-free graphs on $n$ vertices is orders of magnitude harder. Commented May 15 at 12:48