If $G, H$ are finite, simple, undirected graphs, their *categorical product* $G\times H$ is defined by $V(G\times H) = V(G)\times V(H)$ and $$E(G\times H) = \big\{\{(v\_1, w\_1),(v\_2,w\_2)\}: v\_i \in V(G)\land w\_i\in V(H) \land \{v\_1, v\_2\} \in E(G) \land \{w\_1,w\_2\}\in E(H)\big\}.$$


A graph is said to be *critical* if removing any vertex reduces its chromatic number.


[Hedetniemi's conjecture](https://en.wikipedia.org/wiki/Hedetniemi%27s_conjecture) states that $\chi(G\times H) = \min\{\chi(G),\chi(H)\}$ for all finite simple undirected graphs $G,H$.


It implies that the categorical product of critical graphs is also critical. But can we prove this without using Hedetniemi's conjecture?



Product of critical graphs and Hedetniemi's conjecture
It doesn't imply that the categorical product of critical graphs is critical, and this is not true. For instance, the complete graph on three vertices, $K\_3$, is 3-critical, but $K\_3 \times K\_3$ is not since it is not just an odd cycle (which is the only type of 3-critical graph).


