How to calculate number of spanning trees of $K_5$ with extra vertex on one edge? 
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.
 A: 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.
A: From Kirchhoff's matrix tree theorem, you can count the number of spanning trees of any graph in polynomial time. Following is the recipe:

*

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

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

*Subtract the first matrix from the second one.

*Delete any row and any column.

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