# Embedding Mazes - Spanning Trees of a Grid Graph

A perfect maze (a maze with a unique solution) can be seen as a tree, where each node corresponds to a cell in the maze, and where edges corresponds to passages (missing walls) between cells. Two special nodes in the tree $s,e$ corresponds to the start-cell and the end-cell of the maze. An example is the following

If we restrict mazes to be quadratic ($n \times n$) mazes like the one shown above, we can also look at mazes as spanning trees of the $n \times n$ grid graph. There are a number of observations one can make about such trees immediately, for example:

1. The number of vertices is $n^2$
2. No vertex has degree more than 4

Another observation, is that the number of vertices of degree 2 has to be large. One way to observe this, is to consider the distance classes of the graph. If all vertices had degree 3 or more, the number of vertices in the distance classes would grow exponentially, which the number of cells in each distance class does not.

My question, which is rather open ended, is if there exists some kind of classification of these trees.

Edit: Thanks to a comment by @joriki, I now know the number of such trees, as given in OEIS sequence A007341.

-
Fair enough: I’ll delete the comment, and this one in a bit. – Brian M. Scott Mar 12 '12 at 18:15
– joriki Mar 12 '12 at 20:49