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

  • $\begingroup$ 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? $\endgroup$
    – codeR
    Commented May 13 at 7:52
  • $\begingroup$ @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!$. $\endgroup$
    – rus9384
    Commented May 13 at 9:07

1 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.

  • $\begingroup$ 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. $\endgroup$
    – rus9384
    Commented May 15 at 12:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.