Let us call a simple undirected graph $G$ *non-traceable* if there is no Hamiltonian path in $G$.


Are there connected non-traceable graphs $G, H$ such that the [Cartesian produc](https://en.wikipedia.org/wiki/Cartesian_product_of_graphs)t $G{\scriptsize\square} H$ has a Hamiltonian path?



Can the cartesian product of two non-traceable graphs be traceable?
Yes, this is possible and one of the smallest counterexamples is on 6 vertices.


Let $G$ be the graph with edges



```
[(0, 1), (0, 2), (0, 'A'), (1, 2), (1, 'B'), (2, 'C')]

```

This is essentially $K\_3$ with 3 new vertices adjacent to each of the vertices
of the $K\_3$. The cartesian square $G\square G$ has hamiltonian path and even
hamiltonian cycle.


