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

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?

• The trees should be labelled. Now note that your first two pictures are really the same: one vertex as a hub. And your third picture isn't labeled. So go back to the drawing board (literally). Feb 20 '19 at 22:53
• Cayley's formula gives the right answer. Feb 20 '19 at 23:05

## 1 Answer

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.