How to calculate number of spanning trees of $K_5$ with extra vertex on one edge?

Question

Here we have $K_5$ complete subgraph that gives $5^3 = 125$ spanning trees (using Cayley's formula).

Adding one vertex to arbitrary edge, gives me this graph for example.

Using Mathematica, it gives me 200 spanning trees. But I don't know how to get this number using simple combinatorics rules etc. What is the simplest method to get the number of spanning trees for this graph?

Thanks.

Answer 1

Each spanning tree of $K_5$ that contains the augmented edge corresponds to a spanning tree of the new graph with both of the new edges added. Each spanning tree of of $K_5$ that doesn’t contain the augmented edge corresponds to two spanning trees of the new graph, one each with each of the new edges added.

$K_5$ has $\binom52=10$ edges, and each spanning tree includes $4$ of them so, each edge is included in $\frac4{10}\cdot125=50$ of the spanning trees. Thus the new graph has $50+2\cdot75=200$ spanning trees.

Answer 2

From Kirchhoff's matrix tree theorem, you can count the number of spanning trees of any graph in polynomial time. Following is the recipe:

1. Construct the degree matrix of the graph - basically $V \times V$ matrix with how many vertices each vertex is connected to on the diagonals and zeros elsewhere.
2. Construct the adjacency matrix of the graph. Another $V \times V$ matrix with a $0$ if two vertices are not connected and $1$ if they are.
3. Subtract the first matrix from the second one.
4. Delete any row and any column.
5. Take the determinant of the resulting matrix.

And this is the number of spanning trees.

---

In your graph, the degree matrix becomes:

$$D = \left(\begin{matrix} 4 & 0 & 0 & 0 &0 & 0\\ 0 & 4 & 0 & 0 &0 & 0\\ 0 & 0 & 4 & 0 &0 & 0\\ 0 & 0 & 0 & 4 &0 & 0\\ 0 & 0 & 0 & 0 &4 & 0\\ 0 & 0 & 0 & 0 &0 & 2\\ \end{matrix}\right)$$

The adjacency matrix:

$$A = \left(\begin{matrix} 0 & 1 & 1 & 1 &1 & 0\\ 1 & 0 & 1 & 1 &1 & 0\\ 1 & 1 & 0 & 1 &1 & 0\\ 1 & 1 & 1 & 0 &0 & 1\\ 1 & 1 & 1 & 0 &0 & 1\\ 0 & 0 & 0 & 1 &1 & 0\\ \end{matrix}\right)$$

$$D-A = \left(\begin{matrix} 4 & -1 & -1 & -1 &-1 & 0\\ -1 & 4 & -1 & -1 &-1 & 0\\ -1 & -1 & 4 & -1 &-1 & 0\\ -1 & -1 & -1 & 4 &0 & -1\\ -1 & -1 & -1 & 0 &4 & -1\\ 0 & 0 & 0 & -1 &-1 & 2\\ \end{matrix}\right)$$

Now delete any row and column and find the determinant. Python code:

a=[[4,-1,-1,-1,-1],[-1,4,-1,-1,-1],[-1,-1,4,-1,-1],[-1,-1,-1,4,0],[0,0,0,-1,-1]]
import numpy as np
np.linalg.det(a)

Gives you 200.