# Spanning forests, electrical networks, and a determinant identity†

Elmar Teufl¹ and Stephan Wagner²

¹Fakultät für Mathematik, Universität Bielefeld, P.O.Box 100131, 33501 Bielefeld, Germany

²Department of Mathematical Sciences, Stellenbosch University, Private Bag X1, Matieland 7602, South Africa

**Abstract.** We aim to generalize a theorem on the number of rooted spanning forests of a highly symmetric graph to the case of asymmetric graphs. We show that this can be achieved by means of an identity between the minor determinants of a Laplace matrix, for which we provide two different (combinatorial as well as algebraic) proofs in the simplest case. Furthermore, we discuss the connections to electrical networks and the enumeration of spanning trees in sequences of self-similar graphs.

**Résumé.** Nous visons à généraliser un théorème sur le nombre de forêts couvrantes d'un graphe fortement symétrique au cas des graphes asymétriques. Nous montrons que cela peut être obtenu au moyen d'une identité sur les determinants mineurs d'une matrice Laplacienne, pour laquelle nous donnons deux preuves différentes (combinatoire ou bien algébrique) dans le cas le plus simple. De plus, nous discutons les relations avec des réseaux électriques et l'énumération d'arbres couvrants dans de suites de graphes autosimilaires.

**Keywords:** spanning forest, electrical network, Laplace matrix, determinant identity

## 1 Introduction

It is known since Kirchhoff's days [10] that there is a close relationship between electrical networks, spanning trees, and the Laplace matrix of a graph. There is a vast amount of literature on spanning trees, electrical networks and related notions: see e.g. [1, 4, 8, 12, 13]. The relation to probability theory was studied in [9, 14]. The celebrated matrix-tree theorem is the most important tool for the enumeration of spanning trees, and it has been successfully used to find closed formulæ for the number of spanning trees in various classes of graphs. A version of the matrix-tree theorem considers all minors of the Laplace matrix of a graph $G$ rather than just those that result from deleting one row and one column. It turns out that the determinants of smaller submatrices count spanning forests of $G$:

**Theorem 1** Let $G = (V, E)$ be a graph and $L = L_G$ its Laplace matrix. For a subset $R \subseteq V$, let $L(R)$ be the matrix that results from deleting all rows and columns that correspond to vertices in $R$. Then, the number $r(R) = r_G(R)$ of rooted spanning forests whose roots are precisely the vertices in $R$ is given by

$$r(R) = \det L(R).$$

<footnote>†This material is based upon work supported by the German Research Foundation DFG under grant number 445 SUA-113/25/0-1 and the South African National Research Foundation under grant number 65972.</footnote>
We refer the interested reader to [5, 6, 15] for a proof of this theorem. This important result was used in a recent paper by the authors [17], in which the following theorem was given as a byproduct:

**Theorem 2** Let G be a connected, finite (multi-)graph and let $D \subseteq V$ be a subset of $\theta$ distinguished vertices. Suppose that G is strongly symmetric with respect to D, i.e. the restriction of the automorphism group of G to D is either the entire symmetric group or the alternating group. Then we have

$$r(R) = k \rho^{k-1} \theta^{1-k} t(G)$$

for all sets $R \subseteq D$ of cardinality $k$, where $\rho$ is the resistance scaling factor of G with respect to D and $t(G)$ is the number of spanning trees of G.

A precise definition of the resistance scaling factor is given in Section 3. The above result was inspired by the problem of enumerating spanning trees in certain sequences of self-similar graphs which in turn was motivated by applications in statistical physics [7]. However, it appeared that the condition “strongly symmetric with respect to the distinguished vertices” is stronger than necessary, and experimentally, it seemed that it could be relaxed to “the automorphism group acts 2-homogeneously on the set of distinguished vertices”. In this paper, we show that this will be a consequence of a certain determinant identity, thus providing a generalization to the case of graphs that lack symmetry. We prove this determinant identity in the simplest case (three distinguished vertices) in two different ways and discuss its implications to the theory of electrical networks and the aforementioned enumeration of spanning trees in sequences of self-similar graphs. The general form of the determinant identity is left as a conjecture to be proved at a later stage. This conjecture reads as follows:

**Conjecture 3** Let G be a (possibly edge-weighted, not necessarily connected) graph and L its weighted Laplace matrix. For a set R of vertices, we write $L(R)$ for the matrix that results from deleting all rows and columns corresponding to R as before. Furthermore, we set $r(R) = \det L(R)$, and $t(G)$ denotes the number of spanning trees of G (counted according to the weights). Then, the identity

$$r(R)t(G)^{|R|-2} = \sum_B \alpha(B) \prod_{\{v,w\} \in E(B)} r(\{v, w\}) \quad (1)$$

holds for all sets R with $|R| \ge 2$, where the sum is taken over all graphs B with vertex set R and the following properties:

* The number of edges of B is exactly $|R| - 1$,

* All components of B are either paths (possibly single vertices) or cycles (which includes the 2-cycle with two edges connecting the same vertices).

The coefficient $\alpha(B)$ is then given by

$$\alpha(B) = \prod_{C \in \mathcal{C}(B)} \beta(C),$$

where $\mathcal{C}(B)$ is the set of all components of B and

$$\beta(C) = \begin{cases} 2^{1-\ell} & \text{if C is a path of length } \ell > 0, \\ -2^{1-\ell} & \text{if C is a cycle of length } \ell > 2, \\ 1 & \text{if C is a single vertex,} \\ -\frac{1}{4} & \text{if C is a 2-cycle.} \end{cases}$$
**Remark 1** Note that $t(G) = r(\{v\})$ for any vertex $v$. Hence, (1) remains true for $|R| = 1$ if the empty product is considered to be 1.

If the graph $G$ is connected (hence $t(G) > 0$), we may write Formula (1) in the form

$$ \frac{r(R)}{t(G)} = \sum_{B} \alpha(B) \prod_{\{v,w\} \in E(B)} \frac{r(\{v,w\})}{t(G)}. $$

Thus the equation above relates the quotient $r(R)/t(G)$ for arbitrary root set $R$ to the same quantities for root sets of size 2. The quantity $r(\{v, w\})/t(G)$ measures the effective resistance between $v$ and $w$, see Section 3 for further information about this.

## 2 Proof of the special case

As mentioned in the introduction, we want to exhibit two different ways to prove our determinant identity in the case of three distinguished vertices. In this simple case, it reads as follows:

$$ r(\{v, w, x\})r(\{v\}) = \frac{1}{2}\left(r(\{v, w\})r(\{v, x\}) + r(\{v, w\})r(\{w, x\}) + r(\{v, x\})r(\{w, x\})\right) - \frac{1}{4}\left(r(\{v, w\})^2 + r(\{v, x\})^2 + r(\{w, x\})^2\right) \quad (2) $$

for arbitrary vertices $v, w, x \in V$.

### 2.1 Combinatorial proof

First, we construct a graph $H$ as follows: let $G$ and $G'$ be disjoint isomorphic copies of $G$, with an isomorphism $\phi: G \to G'$. The vertices in $G'$ that correspond to $v, w, x$ are denoted by $v', w', x'$. Now, we identify $v$ and $v'$, $w$ and $w'$, and $x$ and $x'$. Furthermore, we impose an additional weight $\lambda$ on all edges of $G$ and an additional weight $\mu$ on all edges of $G'$ (note that edges connecting $v, w, x$ are doubled and thus receive a weight of $\lambda + \mu$). If the Laplace matrix of $G$ has the shape

$$ L_G = \begin{pmatrix} L_1 & L_2 \\ L_3 & L_4 \end{pmatrix}, $$

where $L_1$ and $L_2$ form the rows corresponding to $v, w, x$, and $L_1$ and $L_3$ form the respective columns, then the Laplace matrix of $H$ has the shape

$$ L_H = \begin{pmatrix} (\lambda + \mu)L_1 & \lambda L_2 & \mu L_2 \\ \lambda L_3 & \lambda L_4 & 0 \\ \mu L_3 & 0 & \mu L_4 \end{pmatrix}. $$

We delete the first row and column to obtain a matrix $\tilde{L}$ of the form

$$ \tilde{L} = \begin{pmatrix} (\lambda + \mu)\tilde{L}_1 & \lambda\tilde{L}_2 & \mu\tilde{L}_2 \\ \lambda\tilde{L}_3 & \lambda\tilde{L}_4 & 0 \\ \mu\tilde{L}_3 & 0 & \mu\tilde{L}_4 \end{pmatrix}. $$
The weighted number of spanning trees of $H$ is given by

$$ \det \tilde{L} = \det \begin{pmatrix} (\lambda + \mu)\tilde{L}_1 & \lambda\tilde{L}_2 & \mu\tilde{L}_2 \\ \lambda\tilde{L}_3 & \lambda L_4 & 0 \\ 0 & -\mu L_4 & \mu L_4 \end{pmatrix} = \det \begin{pmatrix} (\lambda + \mu)\tilde{L}_1 & (\lambda + \mu)\tilde{L}_2 & \mu\tilde{L}_2 \\ \lambda\tilde{L}_3 & \lambda L_4 & 0 \\ 0 & 0 & \mu L_4 \end{pmatrix} \\ = (\lambda + \mu)^2 \lambda^{|V|-3} \mu^{|V|-3} \det \begin{pmatrix} \tilde{L}_1 & \tilde{L}_2 \\ \tilde{L}_3 & L_4 \end{pmatrix} \det L_4. $$

Note that the coefficient of $\lambda^{|V|-2}\mu^{|V|-2}$ gives those spanning trees which contain $|V|-2$ edges in $G$ and $|V|-2$ edges in $G'$ and thus induce two spanning forests with two components each on $G$ and $G'$. From the above expression for the determinant, it is obvious that this coefficient is exactly

$$ 2 \det \begin{pmatrix} \tilde{L}_1 & \tilde{L}_2 \\ \tilde{L}_3 & L_4 \end{pmatrix} \det L_4 = 2r(\{v\})r(\{v, w, x\}). $$

This means that the left hand side of (2) is also the (weighted) number of unordered pairs $(F_1, F_2)$ of spanning forests with two components in $G$ resp. $G'$ and the property that their union is a spanning tree in $H$ (note that $\phi(F_1) \neq F_2$ for such a pair, since this would yield a cycle, and thus the number of unordered pairs is indeed just $\frac{1}{2}$ of the number of ordered pairs). We want to show that this is exactly the right hand side of (2). Each component of $F_1$ and $F_2$ has to contain at least one of the vertices $v, w, x$, since their union forms a spanning tree, and they are only joined at $v, w, x$. The right hand side of (2) only counts pairs of (rooted) spanning forests with this property by definition, hence it suffices to consider such spanning forests.

Now we only have to show that an unordered pair $(F_1, F_2)$ of spanning forests with two components each of which contains at least one vertex of $\{v, w, x\}$ is counted with coefficient 1 on the right hand side of (2) if the union is a spanning tree and with coefficient 0 otherwise. We distinguish three cases:

* $F_1$ and $F_2$ induce distinct connections on the set $\{v, w, x\}$, so that the union forms a spanning tree. Without loss of generality, we assume that $F_1$ connects $v$ and $w$, while $F_2$ connects $v$ and $x$. Then, $F_1$ can be rooted at $v$ and $x$ or at $w$ and $x$, and $F_2$ can be rooted at $v$ and $w$ or at $w$ and $x$. The four possibilities yield a total coefficient of 1:

<table><thead><tr><th>roots of F<sub>1</sub></th><th>roots of F<sub>2</sub></th><th>coefficient</th></tr></thead><tbody><tr><td>v, x</td><td>v, w</td><td><sup>1</sup>&frasl;<sub>2</sub></td></tr><tr><td>v, x</td><td>w, x</td><td><sup>1</sup>&frasl;<sub>2</sub></td></tr><tr><td>w, x</td><td>v, w</td><td><sup>1</sup>&frasl;<sub>2</sub></td></tr><tr><td>w, x</td><td>w, x</td><td>-2 &middot; <sup>1</sup>&frasl;<sub>4</sub></td></tr></tbody></table>

* $F_1$ and $F_2$ induce the same connections on the set $\{v, w, x\}$, so that a cycle is formed, but $\phi(F_1) \neq F_2$. Without loss of generality, we assume that $F_1$ and $F_2$ connect $v$ and $w$. Again, we have to consider four possibilities:
<table><thead><tr><th>roots of F<sub>1</sub></th><th>roots of F<sub>2</sub></th><th>coefficient</th></tr></thead><tbody><tr><td>v, x</td><td>v, x</td><td>-2 &middot; <sup>1</sup>&frasl;<sub>4</sub></td></tr><tr><td>v, x</td><td>w, x</td><td><sup>1</sup>&frasl;<sub>2</sub></td></tr><tr><td>w, x</td><td>v, x</td><td><sup>1</sup>&frasl;<sub>2</sub></td></tr><tr><td>w, x</td><td>w, x</td><td>-2 &middot; <sup>1</sup>&frasl;<sub>4</sub></td></tr></tbody></table>

The total coefficient is 0, as desired.

* $\phi(F_1) = F_2$. Suppose for instance that $F_1$ connects $v$ and $w$. As in the previous case, the union is not a spanning tree, and again, we obtain a coefficient 0:

<table><thead><tr><th>roots of F<sub>1</sub></th><th>roots of F<sub>2</sub></th><th>coefficient</th></tr></thead><tbody><tr><td>v, x</td><td>v, x</td><td>-<sup>1</sup>&frasl;<sub>4</sub></td></tr><tr><td>v, x</td><td>w, x</td><td><sup>1</sup>&frasl;<sub>2</sub> &middot; <sup>1</sup>&frasl;<sub>2</sub></td></tr><tr><td>w, x</td><td>v, x</td><td><sup>1</sup>&frasl;<sub>2</sub> &middot; <sup>1</sup>&frasl;<sub>2</sub></td></tr><tr><td>w, x</td><td>w, x</td><td>-<sup>1</sup>&frasl;<sub>4</sub></td></tr></tbody></table>

Putting everything together, we reach the desired result.

## 2.2 Algebraic proof

We are now going to derive Formula (2) using basic linear algebra and the Desnanot-Jacobi identity (also known as condensation formula, see for example [3]): For simplicity we assume that the vertex set $V$ is given by $V = \{1, 2, \dots, n\}$ with $v = 1, w = 2, x = 3$. Furthermore, we write $L_B^A$ to denote the submatrix of $L$ obtained by deleting the rows in $A \subseteq V$ and columns in $B \subseteq V$ and set $D_B^A = \det(L_B^A)$. Then Formula (2) reads as follows:

$$D_1^1 D_{1,2,3}^{1,2,3} = \frac{1}{2} \left( D_{1,2}^{1,2} D_{1,3}^{1,3} + D_{1,2}^{1,2} D_{2,3}^{2,3} + D_{1,3}^{1,3} D_{2,3}^{2,3} \right) - \frac{1}{4} \left( (D_{1,2}^{1,2})^2 + (D_{1,3}^{1,3})^2 + (D_{2,3}^{2,3})^2 \right)$$

In order to prove this identity we start with the following simple observation: Let $b_1, b_2, \dots, b_n$ be the column vectors of $L^{1,2}$. Then $b_1 + b_2 + b_3 + b_4 + \dots + b_n = 0$, since the sum of column vectors in $L$ is equal to 0. Hence

$$ \begin{aligned} 0 &= \det(b_1 + b_2 + b_3, b_4, \dots, b_n) \\ &= \det(b_3, b_4, \dots, b_n) + \det(b_2, b_4, \dots, b_n) + \det(b_1, b_4, \dots, b_n) = D_{1,2}^{1,2} + D_{1,3}^{1,2} + D_{2,3}^{1,2}. \end{aligned} $$

By symmetry of $L$ the minors $D_{2,3}^{1,2}$ and $D_{1,2}^{2,3}$ are equal. Thus

$$D_{1,2}^{1,2} + D_{1,3}^{1,2} + D_{1,2}^{2,3} = 0.$$

Similarly, we find that

$$D_{1,3}^{1,2} + D_{1,3}^{1,3} + D_{1,3}^{2,3} = 0 \quad \text{and} \quad D_{1,2}^{2,3} + D_{1,3}^{2,3} + D_{2,3}^{2,3} = 0.$$
Adding the first two equations and subtracting the last one we obtain

$$2D_{1,3}^{1,2} = D_{2,3}^{2,3} - D_{1,2}^{1,2} - D_{1,3}^{1,3}. \qquad (3)$$

By the Desnanot-Jacobi identity we have

$$D_{1,2,3}^{1,2,3} D_1^1 = D_{1,2}^{1,2} D_{1,3}^{1,3} - D_{1,3}^{1,2} D_{1,2}^{1,3} = D_{1,2}^{1,2} D_{1,3}^{1,3} - (D_{1,3}^{1,2})^2, \qquad (4)$$

where $D_{1,3}^{1,2} = D_{1,2}^{1,3}$ by symmetry of $L$. By inserting (3) into (4) we finally obtain the asserted identity.

**Remark 2** Let us note that we have verified Conjecture 3 for the case of four and five boundary vertices using a similar algebraic argument and a more general version of the Desnanot-Jacobi identity (see [11]).

## 3 Electrical networks

Let $G = (V, E, c)$ be an edge-weighted graph (network) with weights (conductances) $c: E \to [0, \infty)$. The (weighted) Laplace matrix $L$ is defined by its entries

$$L_{x,y} = \begin{cases} -c(\{x, y\}) & \text{if } x \neq y, \\ \sum_{z \sim x} c(\{x, z\}) & \text{if } x = y \end{cases}$$

for all vertices $x, y \in V$. We say that two networks $(V(G), E(G), c_G)$ and $(V(H), E(H), c_H)$ are *electrically equivalent* with respect to $D \subseteq V(G) \cap V(H)$, if they cannot be distinguished by applying voltages to $D$ and measuring the resulting currents on $D$. By Kirchhoff's current law this means that the rows corresponding to $D$ of $L_G H_D^{V(G)}$ and $L_H H_D^{V(H)}$ are equal, where $H_D^{V(G)}$ is the matrix associated to harmonic extension. If $u, v \in V(G)$ are vertices in $G$ and $H$ is the complete graph with vertex set $\{u, v\}$, then there exists a conductance $c_{\text{eff}}(u, v)$ on the single edge of $H$, so that $(V(G), E(G), c_G)$ and $H$ equipped with $c_{\text{eff}}(u, v)$ are equivalent. The number $\rho_{\text{eff}}(u, v) = c_{\text{eff}}(u, v)^{-1}$ is called *effective resistance* of $u$ and $v$.

In combinatorics unit conductances are of great interest because of the well-known relation between electrical networks and the number of spanning trees. Let $G$ be a graph and $c_G$ be unit conductances on the edges of $G$. We say that $G$ has *resistance scaling factor* $\rho = \rho_D$ with respect to $D \subseteq V$, if $(G, c_G)$ is electrically equivalent to $(H, \rho^{-1}c_H)$, where $H$ is a complete graph with vertex set $V(H) = D$ and $c_H$ are unit conductances on $H$. Note that the effective resistance of vertices $u$ and $v$ in a graph with unit conductances is exactly the resistance scaling factor with respect to $\{u, v\}$.

Theorem 2 implies that the effective resistance of two vertices $u, v$ in a connected graph with unit conductances is given by

$$\rho_{\text{eff}}(u, v) = \frac{r_G(\{u, v\})}{t(G)}. \qquad (5)$$

This can also be obtained from Kirchhoff's famous result connecting currents and spanning trees (see for example [2]). Now Conjecture 3 allows the following interpretation: given all effective resistances of a graph, we can determine all quotients of the form

$$\frac{r_G(R)}{t(G)}.$$
In particular, if two graphs $G$ and $H$ are electrically equivalent with respect to $D$, then

$$ \frac{r_G(R)}{t(G)} = \frac{r_H(R)}{t(H)} $$

for all $R \subseteq D$ (note that Theorem 2 is the special case when $H = K_\theta$). If we pursue this thought to its climax, we finally end up with the following question: Given all effective resistances of a graph, can we reconstruct the original graph?

Of course, we may state this question more generally for networks: Let $G$ be a complete graph on $n$ vertices and conductances on the edges. Clearly the conductances comprise a tuple of $\binom{n}{2}$ non-negative numbers. Given the conductances we can compute all effective resistances in this network easily. The effective resistances also form a tuple of $\binom{n}{2}$ non-negative numbers. Hence we may ask whether it is possible to reverse this computation.

**Conjecture 4** Given effective resistances for each pair of vertices of a complete graph, there is exactly one tuple of conductances, which yields the given effective resistances, and there is a formula similar to (1) that determines them.

It is plausible that this or similar problems have been considered in physics and related fields. Yet we were unable to find anything in the literature we studied, and the expert colleagues we discussed the problem with were not aware of any results in this direction either.

If we are given the numbers $t(G)$ and $r_G(\{u, v\})$ for all $u, v \in V(G)$ of a connected graph, we can compute all effective resistances of $G$ by means of (5). Assuming that the conjecture above holds, we can now reconstruct the network and hence the graph. With full information it is finally easy to compute the numbers $r_G(R)$ for all $R \subseteq V(G)$. Hence Conjecture 3 is plausible, if Conjecture 4 holds.

Let us briefly discuss Conjecture 4 for $n = 3$: Let $V = \{u, v, w\}$. A simple computation yields that

$$ \begin{align*} c_{\text{eff}}(u, v) &= c(\{u, v\}) + \frac{c(\{v, w\})c(\{w, u\})}{c(\{v, w\}) + c(\{w, u\})} = \frac{t(G)}{c(\{v, w\}) + c(\{w, u\})}, \\ c_{\text{eff}}(v, w) &= c(\{v, w\}) + \frac{c(\{w, u\})c(\{u, v\})}{c(\{w, u\}) + c(\{u, v\})} = \frac{t(G)}{c(\{w, u\}) + c(\{u, v\})}, \\ c_{\text{eff}}(w, u) &= c(\{w, u\}) + \frac{c(\{u, v\})c(\{v, w\})}{c(\{u, v\}) + c(\{v, w\})} = \frac{t(G)}{c(\{u, v\}) + c(\{v, w\})} \end{align*} $$

noting that $t(G) = c(\{u, v\})c(\{v, w\}) + c(\{v, w\})c(\{w, u\}) + c(\{w, u\})c(\{u, v\})$. From this it is easy to deduce that given effective conductances $c_{\text{eff}}(u, v)$, $c_{\text{eff}}(v, w)$, and $c_{\text{eff}}(w, u)$ there is at most one solution for the conductances $c(\{u, v\})$, $c(\{v, w\})$, and $c(\{w, u\})$ of the system above (that can be given explicitly). Finally, a simple manipulation shows that

$$ c(\{u, v\}) = \frac{1}{2}t(G)(\rho_{\text{eff}}(\{u, w\}) + \rho_{\text{eff}}(\{v, w\}) - \rho_{\text{eff}}(\{u, v\})), $$

or

$$ c(\{u, v\}) = \frac{1}{2}(r_G(\{u, w\}) + r_G(\{v, w\}) - r_G(\{u, v\})), $$

which shows a certain resemblance to Equation (1).
# 4 Enumeration of spanning trees

Recently, it was shown in two papers independently [7, 16] how the number of spanning trees in Sierpiński graphs (i.e., the finite approximations to the Sierpiński gasket) can be calculated. If $S_n$ denotes the level-$n$ Sierpiński graph (starting with $S_0 = K_3$, see Figure 1), the number of spanning trees is given by the formula

<figure><img src="image_1.png" /><figcaption>Fig. 1: Sierpiński graphs</figcaption></figure>

$$t(S_n) = \sqrt[4]{\frac{3}{20}} \cdot \left(\frac{5}{3}\right)^{-n/2} \cdot \left(\sqrt[4]{540}\right)^{3n} \quad (6)$$

The proofs given in [7, 16] make extensive use of symmetry; in this section, we show that all that is essentially needed is electrical equivalence. To this end, we consider a modified version $T_0, T_1, T_2, \dots$ of the Sierpiński graphs (see Figure 2). Obviously, the resulting graphs are not as symmetric as the Sierpiński graphs and we note that the arguments of [7, 16] are not applicable anymore. We do not only modify the initial graph but also change the number of subdivisions in the construction, since for the simpler construction rule of Sierpiński graphs not all possible phenomena occur. It is not difficult to see that the initial graph $T_0$ is electrically equivalent to a $K_3$ (with unit conductances) with respect to the three corner vertices, and thus this is also the case for all graphs $T_n$ in the sequence (up to a resistance scaling factor of $(\frac{15}{7})^n$, which is easily shown by induction). We write $x_{1,n}, x_{2,n}, x_{3,n}$ for the corner vertices of $T_n$; then, if $H_n$ is the complete graph with vertices $x_{1,n}, x_{2,n}, x_{3,n}$ and edge weights (conductances) $(\frac{7}{15})^n$, we have

$$\frac{r_{T_n}(R)}{t(T_n)} = \frac{r_{H_n}(R)}{t(H_n)}$$

for all subsets $R \subseteq \{x_{1,n}, x_{2,n}, x_{3,n}\}$ of cardinality 2, since the effective resistances are the same. But this is trivially true for subsets of cardinality 1, and the special case of Conjecture 3 for three vertices shows that it is also the case for $R = \{x_{1,n}, x_{2,n}, x_{3,n}\}$.

Now consider the graph $T_{n+1}$, which comprises of six copies of $T_n$. Fix one of these copies and call it $C$. The graph induced by the remaining edges is called $B$. Every spanning tree of $T_{n+1}$ induces spanning forests on $B$ and $C$. Now fix a spanning forest $F$ on $B$ that can be extended to a spanning tree of $T_{n+1}$. $F$ induces certain connections on the corner vertices $u, v, w$ of $C$: If the corner vertices of $C$ are not connected at all by $F$, a spanning tree on $C$ is needed to complete a spanning tree on $T_{n+1}$. If $F$ connects precisely two of the corner vertices of $C$ (say $u$ and $v$), then we need a spanning forest with two components and the property that $u$ and $v$ are in different components. However, this can also be interpreted as a rooted spanning forest with roots $u$ and $v!$ If all corner vertices of $C$ are connected
<figure><img src="image_2.png" /><figcaption>Fig. 2: Modified Sierpiński graphs with three subdivisions</figcaption></figure>

“from the outside” by F, then we need a rooted spanning forest with three components on C to complete a spanning tree, where the roots are precisely the corner vertices again. Hence there are coefficients $\nu_R$ such that

$$t(T_{n+1}) = \sum_{R \subseteq \{u,v,w\}} \nu_R \cdot r_C(R),$$

and these coefficients only depend on B. Note that the coefficient $\nu_{\{u,v,w\}}$ is 0 in the case of ordinary Sierpiński graphs (Figure 1), which is the reason why we deal with three subdivisions instead of two. If we replace C by $H_n$ now to obtain a graph $T'_{n+1}$, the above considerations show that

$$ \begin{aligned} t(T'_{n+1}) &= \sum_{R \subseteq \{u,v,w\}} \nu_R \cdot r_{H_n}(R) = \frac{t(H_n)}{t(C)} \cdot \sum_{R \subseteq \{u,v,w\}} \nu_R \cdot r_C(R) \\ &= \frac{t(H_n)}{t(C)} \cdot t(T_{n+1}) = \frac{t(H_n)}{t(T_n)} \cdot t(T_{n+1}). \end{aligned} $$

Applying this procedure repeatedly for all three copies of $T_n$, we obtain

<figure><img src="image_3.png" /><figcaption>Fig. 3: Replacing $T_n$ by $H_n$</figcaption></figure>

$$t(T_{n+1}) = \left( \frac{t(T_n)}{t(H_n)} \right)^6 \cdot t(Y_{n+1}),$$
where $Y_{n+1}$ comprises of three copies of $H_n$, as indicated in Figure 3. But $H_n$ and $Y_{n+1}$ are small graphs for which the (weighted) number of spanning trees is easily computed explicitly: one has

$$t(H_n) = 3 \cdot \left(\frac{7}{15}\right)^{2n} \quad \text{and} \quad t(Y_{n+1}) = 5292 \cdot \left(\frac{7}{15}\right)^{9n}$$

and thus

$$t(T_{n+1}) = \frac{196}{27} \cdot \left(\frac{15}{7}\right)^{3n} \cdot t(T_n)^6.$$

Now it is just an easy induction to show that

$$t(T_n) = \left( \frac{3^{12}}{2^{10} \cdot 5^3 \cdot 7^7} \right)^{1/25} \cdot \left( \frac{15}{7} \right)^{-3n/5} \cdot \left( \left( \frac{2^{10} \cdot 5^3 \cdot 7^7}{3^{12}} \right)^{1/25} t(T_0) \right)^{6n}$$

In the case of the sequence depicted in Figure 2, we have $t(T_0) = 12$ and obtain

$$t(T_n) = \left( \frac{3^{12}}{2^{10} \cdot 5^3 \cdot 7^7} \right)^{1/25} \cdot \left( \frac{15}{7} \right)^{-3n/5} \cdot \left( 2^{60} \cdot 3^{12} \cdot 5^3 \cdot 7^7 \right)^{6n/25}$$

In a similar way, one can derive Equation (6) for the number of spanning trees of the ordinary Sierpiński graphs. The essential point in this approach was the fact that the graphs $S_0, S_1, \dots$ and $T_0, T_1, \dots$ were electrically equivalent to simple graphs with resistances that could be determined explicitly. If this is not the case any more, things become more complicated, as can be seen from the final example below. Nonetheless, we believe that the technique of replacing subgraphs by electrically equivalent graphs can be very useful for the enumeration of spanning trees (and we also conjecture that it is applicable in general, not just in the case of three boundary vertices).

<figure><img src="image_4.png" /><figcaption>Fig. 4: Another modification of the Sierpiński graphs</figcaption></figure>

Let us now consider the sequence of self-similar graphs depicted in Figure 4. We can still replace the four copies of $U_n$ in $U_{n+1}$ by simple complete graphs $H_n \simeq K_3$ to obtain a graph $Y_{n+1}$, but the conductances in $H_n$ are not all equal any longer. The effective conductances in $U_n$ can be found by iterating the map that is shown in Figure 5: starting with $(a_0, b_0) = (1, 1)$, one applies the recursion

$$(a_{n+1}, b_{n+1}) = \left( \frac{(2a_n + b_n)(3a_n^2 + 8a_n b_n + b_n^2)}{2(3a_n + 2b_n)(3a_n + 5b_n)}, \frac{b_n(2a_n + b_n)}{3a_n + 2b_n} \right)$$
<figure><img src="image_5.png" /><figcaption>Fig. 5: The map that defines the conductances recursively</figcaption></figure>

to obtain the effective conductances $(a_{n+1}, b_{n+1})$ of $U_{n+1}$ from those of $U_n$. Arguing as in the previous example, one obtains

$$t(U_{n+1}) = \left( \frac{t(U_n)}{t(H_n)} \right)^4 \cdot t(Y_{n+1}).$$

Now one has

$$t(H_n) = b_n(2a_n + b_n) \quad \text{and} \quad t(Y_{n+1}) = 2b_n^3(2a_n + b_n)^3(a_n + 3b_n)$$

and thus

$$t(U_{n+1}) = \frac{2(a_n + 3b_n)}{b_n(2a_n + b_n)} \cdot t(U_n)^4.$$

There are no simple formulæ for $a_n$ and $b_n$, but one can show that they behave asymptotically like

$$a_n = A \cdot \left(\frac{5}{9}\right)^n \left(1 + O\left(\left(\frac{2}{3}\right)^n\right)\right), \quad b_n = 3A \cdot \left(\frac{5}{9}\right)^n \left(1 + O\left(\left(\frac{2}{3}\right)^n\right)\right)$$

for some constant $A$, which results in the following asymptotic behavior for $t(U_n)$:

$$t(U_n) \sim B \cdot \left(\frac{9}{5}\right)^{-n/3} \cdot C^{4n}$$

for certain constants $B$ and $C$. Note that the structure of this asymptotic formula is still the same as for the sequence of Sierpiński graphs.

## Acknowledgment

We would like to thank Christian Krattenthaler for pointing out the algebraic proof of the determinant identity and for providing references.

## References

[1] N. Alon. The number of spanning trees in regular graphs. *Random Structures Algorithms*, 1(2):175–181, 1990.

[2] B. Bollobás. *Modern graph theory*, volume 184 of *Graduate Texts in Mathematics*. Springer-Verlag, New York, 1998.
[3] D. M. Bressoud. *Proofs and confirmations*. MAA Spectrum. Mathematical Association of America, Washington, DC, 1999.

[4] R. Burton and R. Pemantle. Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances. *Ann. Probab.*, 21(3):1329–1371, 1993.

[5] S. Chaiken. A combinatorial proof of the all minors matrix tree theorem. *SIAM J. Algebraic Discrete Methods*, 3(3):319–329, 1982.

[6] S. Chaiken and D. J. Kleitman. Matrix tree theorems. *J. Combinatorial Theory Ser. A*, 24(3):377–381, 1978.

[7] S.-C. Chang, L.-C. Chen, and W.-S. Yang. Spanning trees on the Sierpinski gasket. *J. Stat. Phys.*, 126(3):649–667, 2007. arXiv:cond-mat/0609453v1.

[8] P. Chebotarev. Spanning forests and the golden ratio. *Discrete Appl. Math.*, 156(5):813–821, 2008.

[9] P. G. Doyle and J. L. Snell. *Random walks and electric networks*, volume 22 of *Carus Mathematical Monographs*. Mathematical Association of America, Washington, DC, 1984. Also available at http://arxiv.org as math.PR/0001057.

[10] G. R. Kirchhoff. Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird. *Ann. Phys. Chem.*, 72(4):497–508, 1847. Gesammelte Abhandlungen, Leipzig, 1882.

[11] B. Leclerc. On identities satisfied by minors of a matrix. *Adv. Math.*, 100(1):101–132, 1993.

[12] R. P. Lewis. The number of spanning trees of a complete multipartite graph. *Discrete Math.*, 197/198:537–541, 1999. 16th British Combinatorial Conference (London, 1997).

[13] R. Lyons. Asymptotic enumeration of spanning trees. *Combin. Probab. Comput.*, 14(4):491–522, 2005.

[14] R. Lyons and Y. Peres. Probability on trees and networks. Cambridge University Press, in preparation. current version available at http://mypage.iu.edu/~rdlyons/, 2009.

[15] J. W. Moon. Some determinant expansions and the matrix-tree theorem. *Discrete Math.*, 124(1-3):163–171, 1994. Graphs and combinatorics (Qawra, 1990).

[16] E. Teufl and S. Wagner. The number of spanning trees of finite sierpinski graphs. In *Fourth Colloquium on Mathematics and Computer Science*, volume AG of *DMTCS Proceedings*, pages 411–414, 2006.

[17] E. Teufl and S. Wagner. The number of spanning trees in self-similar graphs. preprint, 2008.