4
$\begingroup$

A caterpillar is a tree with the property that if all the leafs are removed then what remains is a path. Could you help me to prove that there are $2^{n-4}+2^{\lfloor n/2\rfloor-2}$ caterpillar on $n$ vertices, $n\geq3$?

(It should use Polya's theorem)

  • 0
    Is $n$ the total number of vertices including leaves, or just the length of the spine?2011-11-26
  • 1
    Also, is the vertex set labeled or not?2011-11-26
  • 0
    @DimitrijeKostic My guess is unlabeled because there are $n!$ labeled paths already and presumably many more caterpillars.2011-11-26
  • 1
    @Henning, the case $n=4$ convinces me we're including the leaves.2011-11-26

2 Answers 2