# 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

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