Counting spanning trees with 5 vertices

1k Views Asked by At

I am trying to count the number of spanning trees for 5 vertices. I am trying to look at the degree of the unlabeled graph.

So for the unlabeled graph with a node of degree 4, there should be ${5 \choose 1}$ ways

for the graph with three vertices of degree 2, there should be $\frac{5!}{2}$ ways

but I have no idea how to count the last unlabeled graph that has a vertex degree of 3 and a vertex degree of 2.

I know that from Cayley's formula the last graph has to have $60$ ways but I want to know how to get to the number $60$.

Thank you in advance for any answer.

1

There are 1 best solutions below

3
On

enter image description here

The vertex labeled $5$ can be chosen in $5$ ways.

The vertex labeled $4$ can be chosen in $4$ ways.

The vertex labeled $3$ can be chosen in $3$ ways.

The last two vertices can be swapped and so there is only one way to label them.