# Hamiltonian circuits on rectangular graphs

Let $$G=(V,E)$$ be a rectangular graph on $$n \times m$$ vertices.

It is easy to show that no Hamiltonian circuit exists for $$n,m$$ odd, and pretty easy to build a circuit for graph with at least one even side.

(Below are my hits on $$6 \times 7$$ rectangular graph)

... and I suppose there are quite a few circuits. (Is it hard to enumerate them, also?)

My main interest, is as follows. Suppose I have a car riding in this "Manhattan"-like city. The car is unaware of true sizes, except, maybe, to which one is even, so it could imagine to itself appropriate circuit on the streets.

Is it true, that being unaware of actual sizes, and equipped with enough memory, there exists a Hamiltonian circuit, which the car with visibility $$= 1$$ is able to follow?

The above circuits seem to be appropriate for cars with visibility $$= 2$$ (except the last one, which I think, requires $$3$$).

Where visibility $$= 1$$ is just seeing $$4$$ immediate neighbors, so not riding in the first column - it has (maybe) no awareness of column index (except it can track for some time, due to memory).

If it helps, I want to move the car in discrete steps, from vertex to vertex.