For what values of $n$ $(n\ge 3)$ is the graph $C_n \times P_n$ planar?

Question

First instinct was that maybe the new graph won't be planar for $n=3$ and $n=5$ because then it might contain a subgraph that is isomorphic to $K_3,_3$ or $K_5$, but I am not sure how to prove that. If that's the case then we probably should also exclude values of $n$ that are multiples of $3$ or $5$.

Then I thought that since we know the properties of the graphs we are combining maybe we can use Euler's formula and show that for certain values of $n$ the requirement $m \le 3n - 6$ doesn't hold.

Answer 1

I assume Op is referring to Cartesian products of graphs. It is easy to find planar drawings of $P_m \times C_n, m, n \geq 3$. (For instance, see Figure 4.3 for a planar drawing of $P_4\times C_7$.)

---

In 1969, Behzad et al. solved the planarity of Cartesian products of graphs.

• M. Behzad, S.E. Mahmoodian, On topological invariants of the product of graphs, Canadian Mathematical Bulletin, 1969, 12(2): 157–166.

THEOREM 4.1. Let $G$ and $H$ be connected graphs on at least three vertices. Then $G \times H$ is planar if and only if both $G$ and $H$ are paths or if one is a path and the other a cycle.