Example pairs of simple non-path graphs with planar Cartesian product

Question

I've been unable to find a pair of simple graphs whose Cartesian product is planar, except where at least one of the pair is a path graph. Do examples exist? If not is such an example impossible?

Answer 1

The graph you seek for does not exist: the Cartesian product of two graphs that are both not path graphs is non-planar. To see this, note that a connected non-path graph is either a cycle or has a vertex with degree at least 3, so the Cartesian product of two non-path graphs must have at least one of the following Cartesian products as subgraphs:

• Cycle □ cycle. These are toroidal grid graphs, which are all non-planar because they contain $K_5$ as a minor, as shown in the following image:
• Cycle □ claw. These are also all non-planar. They contain as a subgraph the product of a claw with a three-vertex path, which itself contains a $K_{3,3}$ minor.
• Claw □ claw. This is a fixed 16-vertex graph, but contains the same product of claw and $P_3$ we showed above to be non-planar. Therefore this graph is non-planar as well.

Since the Cartesian product of two non-path graphs must contain at least one of the above non-planar graphs, all such products must be non-planar.