# Graph Theory Number of 4 cliques from 10 3 cliques

I am try to find a rigorous way to prove that given a graph that has exactly 10 3 cliques(triangles), the maximum number of 4 cliques that can be formed is 3. Or more generally if there is connection with the number of (k-1) cliques and the maximum number of k cliques.

-

I don't think the question is correct. Consider $K_5$ (complete graph on $5$ vertices). It has $\binom{5}{3} = 10$ $3$-cliques and $\binom{5}{4}=5$ $4$-cliques.

A crude bound for general case can be obtained as shown below. But I don't think is a good bound, i.e., the bounds might not be tight for any graph.

Each $k$ clique contains $k$ number of $k-1$ cliques in it. And any two $k$ cliques can have at most one $k-1$ clique common. Using these two observations we can get some crude bound.

Suppose the number of $k$ cliques is $r$. Then the first $k$ clique has $k$ number of $k-1$ cliques in it. The next $k$ clique again has $k$ number of $k-1$ cliques, but at most one of them is common with the first $k$ clique. So it has at least $k-1$ new $k-1$ cliques. Similarly the third one will have at least $k-2$ new $k-1$ cliques and so on.

Now, we get a lower bound for number of $k-1$ cliques (say $R$) in terms of $r$ as,

if $r \geq k$,

$$R \geq k(k-1)/2$$

if $r < k$

$$R \geq k+(k-1)+ \ldots +(k-r+1) = rk - r(r-1)/2$$

-
Good answer. In my question I was thinking the clique number of graph to be 4, so I said 3 4 cliques is the max. But I don't really need this restriction. – epinephelus Mar 6 '13 at 14:34