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?

  • 3
    $\begingroup$ 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). $\endgroup$ Feb 20 '19 at 22:53
  • 1
    $\begingroup$ Cayley's formula gives the right answer. $\endgroup$
    – saulspatz
    Feb 20 '19 at 23:05

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.