The Knights of Ni have asked Roger the Shrubber
to build them a shrubbery maze, somewhat like the famous one at
Hampton Court in England. The maze is to be made on an n by n square
grid, by placing shrubbery to make certain edges impassible, but leaving
a path from the boundary to a goal point on the inside. (See the example
below.) Their conditions are:

— Every boundary edge but one must be shrubbery.
— Every square of the grid must have at least one shrubbery edge.
— The graph made by the shrubbery edges must be a tree (connected, no cycles).

A correct but suboptimal algorithm to search the Hampton Court maze has
long been known: Put your right hand into the shrubbery at the right of the
entrance, then walk forward while keeping your right hand on the shrubbery.

(a) Prove that this RIGHT-HAND-RULE will cause you to walk through every
square of any maze meeting the Knights’ conditions.

(b) For each of the Knights’ three conditions, give an example of a maze that
fails that condition, meets the other two, and is not solved by the right-hand rule.

(c) The DUAL GRAPH of such a maze has a node in the center of each grid
square, and an edge between the centers of any two adjacent squares unless
travel between then is blocked (see the diagram below). Show that for any maze
meeting the Knights’ conditions, there exists a depth-first search of the dual
graph that visits every square of the grid, using the same route as the tour of
the maze given by the right-hand rule.