Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

A Maze, and the corresponding tree.

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.

share|improve this question
    
Fair enough: I’ll delete the comment, and this one in a bit. –  Brian M. Scott Mar 12 '12 at 18:15
1  
See OEIS sequence A007341. –  joriki Mar 12 '12 at 20:49
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.