possible contradiction to Cayley's formula (how many possible labeled trees with n vertices)

176 Views Asked by At

I am supposed to solve the following question, but my answer does not follow Cayley's formula.

Question: how many possible trees are there with $4$ vertices

My answer is $17$, but Cayley's formula states there would only be $16$.

here is an image with my work for this problem

the question does not specify where the tree is labeled or unlabeled

can someone tell me where I messed up on this problem?

1

There are 1 best solutions below

0
On

There are 4 different star graphs, one centered at each vertex. Then, to count the path graphs, there are 4!/2, there are 4! to order the vertices, and two ways to list each path graph, such as 1234 $\equiv$ 4321.

And 4+4!/2=16.