The Number of Paths in a Directed Graph

Suppose I have a directed graph $G = (V,E)$. Suppose that $v_1$ and $v_2$ are two nodes in the graph. Am I correct the number of simple paths (that is, it has no cycles) from $v_1$ to $v_2$ is $O(E)$? Is it true for the special case of directed acyclic graphs?

Bob

That's not true even for DAGs: consider the following, with all edges directed left-to-right:

  o   o   o ... o
/ \ / \ /       \
x   o   o   ...   y
\ / \ / \       /
o   o   o ... o


There are $2^{|E|/4}$ paths from $x$ to $y$. In a graph with cycles, it can be even worse: consider a clique.

• I thank you for your correct response. I think the real problem is that I asked the wrong question.
– Bob
Mar 3, 2018 at 16:58
• Ah, well that's a shame. But if you make a new post with the right question, I'll answer that one too, if I can. :-) Mar 3, 2018 at 20:52