Facts about spanning trees
This page contains some facts about the number of
spanning graphs in a P_n x P_m graph, which were
posted to rec.puzzles
by Noam Elkies. Someone
posted the following question:
Yes! As a child I became lost in a hedge maze. When finally found, my
father explained the left (or right) hand rule. After this, I found that
I liked mazes quite a bit. I do not know what exists in the literature
about mazes, or even if my terminology is correct, but if a labyrinth means
a rectangular maze where any two 'squares' are connect by exactly one
'path', then my question is:
I replied with the remark that this is equal to the number of
spanning trees in a P_n x P_m graph, and pointed to my
How many mazes are there for an m x n rectangle?
Noam Elkies, however, gave the following reply:
Remarkably this has a nontrivial closed-form answer. In general
the number of spanning trees of a graph is the determinant
of the matrix D-A where D is the diagonal matrix of degrees
of the graph and A is the adjacency matrix. Well, not quite --
that matrix has determinant zero (the all-ones vector is in
the nullspace), so omit the first row and column. For the
graph in question the eigenfunctions of D-A, and thus also
the eigenvectors, can be written explicitly as trigonometric
functions; the product of all the nonzero eigenvectors divided
by m*n then gives the answer.
And then posted the next follow-up:
...but (i) of course it's eigenvalues one must multiply,
not eigenvectors, and (ii) I neglected to actually give
the eigenvalues to be multiplied. Barring silly computational
errors, these eigenvalues are
4 * [ sin^2(a pi / 2 m) + sin^2(b pi / 2 n) ]
where a,b are nonnegative integers, not both zero, and less
than m,n respectively.
A few further notes about these numbers: if (say) m is given
then the number of spanning trees as a function of n satisfies
a constant linear recurrence; for instance if m=2 the counts
are 1, 4, 15, 56, 209, 780, 2911, 10864, 40545, 151316, ...
satisfying c(n) = 4 c(n-1) - c(n-2). Finally, the number
of *square* mazes is itself a square up to small factors;
for instance there are
2^34 3^2 5^3 11^4 19^4 41^2 59^2 101^2 181^2 281^2
square mazes of order 10.
I send him the following question by email:
- What exactly is the "small factor" as a function of n?
- Why do these huge numbers factor into such small primes?
- We have not accounted for symmetries: mazes related by
reflection or (in the square case) rotations are regarded
as distinct. What are the counts if we identify such mazes;
equivelntly, for each symmetry of the square or rectangle
how many mazes have that symmetry?
I am not a real mathematician. I would be interested to see a
reference to what you wrote. Do you think it is related to the
method I use? Did you ever look into spanning trees with the
additional restriction that each vertex has either degree 1 or 3?
And he replied with:
Yes -- it's the same determinant formula, except that here the
eigenfunctions and associated eigenvalues can be written
explicitly. (The eigenfunctions are f(a,b)=g(a)*h(b) where
g,h are eigenfunctions of the D-A matrix for a path of length
m,n respectively; the eigenvalue of f is the sum of those
for g and h, whence the formula I posted in a subsequent
message.) I'm not very good at keeping track of references
for such things, though I think
Knuth wrote something along these
lines some years ago. I don't know if there's a good way to
enumerate spanning trees of odd degree, except when the graph
has an odd number of vertices in which case a parity argument
makes such a tree impossible. If you post a query to
sci.math.research you'll likely get a more definitive answer
to both questions.
home and email