Krdytkyu

It's written in this paper by Alon and Lubetzky that $omega(G times H) leq min{omega(G), omega(H)}$, where $omega$ denotes the clique number, and $times$ denotes the tensor product on a graph, where $((a, b), (c, d))$ is an edge in $G times H$ iff $(a, c)$ is an edge in $G$ and $(b, d)$ is an edge in $H$.

I am wondering if there are any examples to the "less than" case of this inequality. How come this isn't an equality? Suppose we take the maximum clique in $G$ and in $H$ and consider all 2-tuples representing vertices in $G times H$ composed of vertices from these cliques. Then based on the definition, by connecting all of these vertices, we can find a new clique in $G times H$ has size which is equal to the smaller of the two clique sizes. So why is there a $leq$?

The bound is always tight. To see this, first note that it’s enough to prove it when $G$ and $H$ are complete graphs and, since $K_m$ is an induced subgraph of $K_n$ (when $mle n$), it’s enough to consider the case $K_mtimes K_m$. But the subgraph induced by the diagonal of $Gtimes G$ is isomorphic to $G$, for any graph $G$.