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