So far I have that the graph's chromatic number is two (not sure how that would help) as well as that since it has an Eulerian circuit, all vertices must have even degree. I am thinking of using Kuratowski's theorem and showing it has no subgraphs homeomorphic to $K_5$ or $K_{3,3}$ but I am unsure how to do that.
Should I start by showing since it is bipartite all of its subgraphs must be bipartite, hence cannot be homeomorphic to $K_5$ or $K_{3,3}$? Or would that be an incorrect approach? Thanks!
Actually yes and there are quite a few of them. How about, for each integer $n$ at least 2, the complete bipartite graph $K_{2n,2n}$ with $2n$ vertices on each side.
Note that $K_{3,3}$ is a subgraph of $K_{2n,2n}$ for all $n \ge 2$ and indeed $K_{3,3}$ is a subgraph of $K_{m,m}$ for all integers odd or even $m \ge 3$ .