# Number of cliques in a graph and intersection number

Define the number of cliques in a graph $G$ to be $c(G)$ and the intersection number of the graph to be $\omega(G)$. I have been tasked to comment on the inequality between $c(G)$ and $\omega(G)$. I believe that $c(G)\geq \omega(G)$. Consider $S_v$ to be the set corresponding to the vertex $v$. Define $C_i=\{v \lvert i\in S_v\}$ for each $i\in S$. Now $C_i$ is a complete subgraph of $G$ and also if $C_i=C_j$ then we can remove $j$ and everything would remain same, thus getting intersection number less than $\omega(G)$ which is impossible.

I think the proof is correct, but I am a little unsure if I can indeed remove $j$, but to complete my task I must give an example where $c(G)>\omega(G)$, I can't seem to find it. Some help would be appreciated. Thanks.

• did you ever find an answer to this? Apr 26 '18 at 23:22

It is known that the number of cliques in a graph is no smaller than the number of edges, i.e. $$c(G) \geq m$$. Also, we know that the number of edges is an upper bound for the intersection number, i.e. $$\omega(G)\leq m$$. Doesn't this imply the proof that you are looking for?