MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $G$ be a finite connected graph on a $2m$-element vertex set $V$. For any graph with vertices $u,v$, let $\mu(u,v)$ denote the number of edges between $u$ and $v$. Suppose that $G$ has an automorphism $f$ that is a fixed-point free involution on the vertices. We can define a quotient graph $G/f$ by letting the vertices of $G/f$ be the orbits $[u]=\left\lbrace u,f(u)\right\rbrace$ of $f$, and setting $$ \mu([u],[v]) = \mu(u,v) + \mu(f(u),v). $$ Let $\kappa(H)$ denote the number of spanning trees of a graph $H$. By the Matrix-Tree Theorem and some simple linear algebra, one can show that $2\kappa(G)$ is divisible by $\kappa(G/f)$. My question is whether the factor of 2 is necessary, i.e., is it always true that $\kappa(G)$ is divisible by $\kappa(G/f)$? Similar questions can be asked for more complicated automorphism groups of $G$.

share|cite|improve this question
I think this works in the general case too if we define a quotient according to $\mu([u],[v])=\mu(u,v)+\mu(u,f(v))+\cdots+\mu(u,f^{n-1}(v))$, where $f$ is an automorphism of degree $n$, but I havent checked the details. I wonder if there are any other graph related quantities that behave this way under taking quotients. – Gjergji Zaimi Jun 4 '10 at 14:40

Let us group the vertices as $U=\{u_1,u_2,\dots,u_n\}$ and $V=\{v_1,v_2,\dots, v_n\}$ where $f(u_i)=v_i$. Let $L_0$ be the laplacian of the graph with vertex set $U$ and edges as restricted from $G$, let $L _1 = \operatorname{diag}\left( \sum _{j=1}^n \mu(u _i, v _j)\right)$ and $L=L _0+L _1$, also let $A$ be the symmetric matrix whose $a _{ij}$ is $-\mu(u _i,v _j)$. Clearly the Laplacian of $G$ is $M=\left( \begin {array} {cc} L & A \\\ A & L \end {array} \right)$. Let $M^*$ stand for the matrix $M$ with deleted first row and column. We have $$\kappa(G)=\det \left( \begin {array} {cc} L & A \\\ A & L \end {array} \right) ^ *=\det \left( \begin {array} {cc} B & C \\\ D & (L+A)^ * \end {array} \right)$$ for some block matrices $B,C,D$ of size $n\times n,n\times (n-1),$ and $(n-1)\times n$ where this second matrix was obtained by adding the $i$th row of $M^{\*}$ to it's $n+i$th row for $1\le i\le n-1$ and then adding the first (or last) $n-1$ columns to the $n$th column. So $D$ is the matrix $(L+A)*$ together with a last column of zeros, making $(L+A)^{\*-1}D$ with integer entries. Next we factor it using one of these identities $$\kappa(G)=\det(L+A)^ * \det(B-C(L+A)^{*-1}D)$$ and observe that $L+A$ is the Laplacian of $G/f$ so $\det(L+A)^ *=\kappa(G/f)$, and since the second factor is an integer we get the desired divisibility.

share|cite|improve this answer
It seems to me that the statement "Clearly the Laplacian of G is M = [[L,A],[A,L]]" is false. Can the proof be fixed? – Richard Stanley May 29 '10 at 21:33
Fortunately it was just a typo, I think it's fixed now. – Gjergji Zaimi May 31 '10 at 5:55
The proof looks o.k. now. Getting the last column of zeros was a key step. Thanks for your answer! – Richard Stanley Jun 21 '10 at 1:12

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.