# Number of spanning trees of a quotient graph

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$.

• 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}$$ entry 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 $$\left((L+A)^*\right)^{-1}D$$ with integer entries. Next we factor it using one of these identities $$\kappa(G)=\det(L+A)^ * \det(B-C\left((L+A)^*\right)^{-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.