Cartesian product of two graphs

Question

How can I show that the number of edges of the Cartesian product of two graphs may be a prime number? Hadwiger number may be useful but I do not know how can I use it

Answer 1

It's always helpful to try some simple examples.

We can look at the graphs $P_3$, i.e. the path on 3 vertices with 2 edges, and $P_2 = K_2$, i.e. the path on 2 vertices with 1 edge. The cartesian product of $P_3$ and $P_2$ is the $3\times 2$ grid. This graph has $3\cdot 2 = 6$ vertices, and 3 horizontal and 4 vertical edges. So it has a total of 7 edges, and 7 is prime.