Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 4 down vote accepted

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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