<p>An undirected acyclic graph is a forest. See here: <a href="https://en.wikipedia.org/wiki/Tree_(graph_theory)" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Tree_(graph_theory)</a></p>
<p>So, a rough upper bound would obviously be n^2 since each 2 vertices have at most 1 path between them.</p>

CC BY-SA 4.0
2021-05-01T23:59:05.453Z
2021-05-02T00:06:57.000Z
2021-05-02T00:06:57.000Z
Avi Tal
<p>I was wondering if there is an upper bound on the total number of fixed-length paths (path length from 1 to <span class="math-container">$n-1$</span> given <span class="math-container">$n$</span> nodes) in an acyclic graph (not directed) of <span class="math-container">$n$</span> nodes? If so, can you point me to some references?</p>
<p><a href="https://cstheory.stackexchange.com/questions/25707/the-complexity-of-counting-simple-paths-in-a-directed-graph">This question</a> explains the counting <span class="math-container">$s-t$</span> path is #P-complete but I'm not sure if the same applies to my question as well.</p>
<p>Thanks!</p>

CC BY-SA 4.0
2021-05-02T00:05:07.167Z
You might get some downvotes due to off-topic...
Avi Tal
CC BY-SA 4.0
2021-05-02T01:38:04.080Z
Why this is off-topic?
xxks-kkk
CC BY-SA 4.0
2021-05-02T03:56:46.003Z
Usually non-research level questions are off topic...     The moderators will probably respond soon.
Avi Tal
CC BY-SA 4.0
2021-05-02T07:46:36.310Z
Thanks for the clarification. That's sad esp. there is no obvious way for me to find out the main purpose of this stack exchange and "theoretical computer science" is subject to interpretation. Should include "research" somewhere in it :(
xxks-kkk
CC BY-SA 4.0
2021-05-02T08:17:12.933Z
The Computer Science forum is probably the appropriate place. I guess you are right... They should have named the TCS forum as "TCS Research"...
Avi Tal
CC BY-SA 4.0
2021-05-02T13:43:46.250Z
As for “no obvious way”, did you read the first few sentences of https://cstheory.stackexchange.com/tour, or the faq https://cstheory.stackexchange.com/help/on-topic it refers to? They both mention research too many times for me to count.
Emil Jeřábek
CC BY-SA 4.0
2021-05-03T09:01:58.903Z
It seems you deleted the comments meanwhile, but for the record, let me give a brief answer. This site is no different from any other SE site. *Every* SE site has a defined scope that determines what questions are on-topic and what are off-topic. A summary is given in a large banner that appears on top of the site whenever you visit the site before creating an account. After that, detailed information about the site can be found under the Help Center icon in the top bar (the ? in a circle); the first link there is the “tour” page.
Emil Jeřábek
CC BY-SA 4.0
2021-05-03T09:22:03.257Z
Great. Thanks for the instruction. It seems like you can keep the comment civil. I think flag your first comment is good enough.
xxks-kkk
<graph-theory>
upper bound on the total number of fixed-length paths in an acyclic graph
xxks-kkk
# upper bound on the total number of fixed-length paths in an acyclic graph

(Asked by: username_0 on 2021-05-01)

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](https://cstheory.stackexchange.com/questions/25707/the-complexity-of-counting-simple-paths-in-a-directed-graph) explains the counting $s-t$ path is #P-complete but I'm not sure if the same applies to my question as well.

Thanks!

**Tags:** graph-theory

> **Comments:**
> **username_1**: You might get some downvotes due to off-topic...  
> **username_0**: Why this is off-topic?  
> **username_1**: Usually non-research level questions are off topic...     The moderators will probably respond soon.  
> **username_0**: Thanks for the clarification. That's sad esp. there is no obvious way for me to find out the main purpose of this stack exchange and "theoretical computer science" is subject to interpretation. Should include "research" somewhere in it :(  
> **username_1**: The Computer Science forum is probably the appropriate place. I guess you are right... They should have named the TCS forum as "TCS Research"...  
> **username_2**: As for “no obvious way”, did you read the first few sentences of https://cstheory.stackexchange.com/tour, or the faq https://cstheory.stackexchange.com/help/on-topic it refers to? They both mention research too many times for me to count.  
> **username_2**: It seems you deleted the comments meanwhile, but for the record, let me give a brief answer. This site is no different from any other SE site. *Every* SE site has a defined scope that determines what questions are on-topic and what are off-topic. A summary is given in a large banner that appears on top of the site whenever you visit the site before creating an account. After that, detailed information about the site can be found under the Help Center icon in the top bar (the ? in a circle); the first link there is the “tour” page.  
> **username_0**: Great. Thanks for the instruction. It seems like you can keep the comment civil. I think flag your first comment is good enough.  

---

## 1 answers

### Answer by username_1 on 2021-05-01. Score: 0 | Accepted answer

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.


---

