Consider a graph where the edges are split into 5 layers, with the first layer being $$$1$$$, second layer $$$2$$$ to $$$\frac{n}{2}-1$$$, third layer $$$\frac{n}{2}$$$, fourth layer $$$\frac{n}{2}+1$$$ to $$$n-1$$$, fifth layer $$$n$$$, and edges between all pairs of vertices in consecutive layers. There would be $$$O(n^2)$$$ possible paths from $$$1$$$ to $$$n$$$, all length $$$4$$$.