I was wondering if there is an upper bound on the total number of fixed-length paths (path length from 1 to $n-1$ given $n$ nodes) in an acyclic graph (not directed) of $n$ nodes? If so, can you point me to some references?

This question explains the counting $s-t$ path is #P-complete but I'm not sure if the same applies to my question as well.


  • $\begingroup$ You might get some downvotes due to off-topic... $\endgroup$ – Avi Tal May 2 at 0:05
  • $\begingroup$ Why this is off-topic? $\endgroup$ – xxks-kkk May 2 at 1:38
  • $\begingroup$ Usually non-research level questions are off topic... The moderators will probably respond soon. $\endgroup$ – Avi Tal May 2 at 3:56
  • 1
    $\begingroup$ The Computer Science forum is probably the appropriate place. I guess you are right... They should have named the TCS forum as "TCS Research"... $\endgroup$ – Avi Tal May 2 at 8:17
  • 1
    $\begingroup$ As for “no obvious way”, did you read the first few sentences of cstheory.stackexchange.com/tour, or the faq cstheory.stackexchange.com/help/on-topic it refers to? They both mention research too many times for me to count. $\endgroup$ – Emil Jeřábek May 2 at 13:43

An undirected acyclic graph is a forest. See here: https://en.wikipedia.org/wiki/Tree_(graph_theory)

So, a rough upper bound would obviously be n^2 since each 2 vertices have at most 1 path between them.


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