Let T = (V , E) be a tree with |V | = n ≥ 2. How many distinct paths are there (as sub graphs) in T?

I already have the answer to this question as (n/2). The problem that I'm having is finding anything in the text that helps me to figure out how to arrive at this answer.


closed as no longer relevant by Gerry Myerson, Chris Godsil, Mark Sapir, Benoît Kloeckner, Brendan McKay Jun 24 '13 at 13:45

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center. If this question can be reworded to fit the rules in the help center, please edit the question.


Any two vertices of a tree are connected by a unique path, so there are exactly $n\choose2$ paths of length at least one.

  • 3
    $\begingroup$ Good job. That wasn't too hard. :-) If you want, you can accept your own answer as the "correct answer". For that, click on the check mark next to your answer. $\endgroup$ – André Henriques Jun 22 '13 at 21:53
  • $\begingroup$ @ButchMalahide: wait what? I think the answer is right, there are n choose 2 paths of length at least one. $\endgroup$ – Zsbán Ambrus Jun 23 '13 at 9:49
  • $\begingroup$ I think maybe the disagreement is semantic, whether we take the length to be the number of vertices or the number of edges. $\endgroup$ – Eric Tressler Jun 23 '13 at 9:51

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