Consider the Graph below: 

How many spanning trees can be found? 

The given graph has $4$ vertices.

Let the vertices be:

$A, B, C, D$

Edges are:

$AB, BC, AD, BD, CD$

So, total edges are $5$.

This graph is like complete graph $K_4$ with one edge missing.

Number of spanning trees in $K_4$ is given by Cayley’s formula:

$4^{4-2}=4^2=16$

In $K_4$, each edge appears in equal number of spanning trees.

Total edge appearances in all spanning trees:

$16 \times 3 = 48$

Because each spanning tree of $4$ vertices has $3$ edges.

Since $K_4$ has $6$ edges, each edge appears in:

$\frac{48}{6}=8$

Now, one edge is missing in the given graph.

So, spanning trees containing that missing edge are removed.

Number of spanning trees:

$16-8=8$