3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ did you ever find an answer to this? $\endgroup$ Apr 26 '18 at 23:22
1
$\begingroup$

It is quite straightforward from the definition. You are comparing the number of cliques, with the minimum number of cliques that have a certain condition (that is, they cover the set of edges of the graph). In other words, you are comparing the size of a set, with the size of its subset.

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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