# Finding a family of graphs that displays a certain characteristic

I've read that the number of distinct paths in a graph can be exponential in relation to the number of vertices, later I encountered a problem which I spent some time trying to solve on my own.

The problem asks to find a family of undirected graphs in such a manner that every graph has a pair of vertices $$s$$ and $$t$$ such that the number of simple paths from $$s$$ to $$t$$ is at least $$\Omega(2^n)$$, where $$n = |V|$$.

I've tried applying this to a clique and a circular graph, but didn't really manage to find two (different) vertices that have this characteristic.

Not sure how to direct my thoughts from here.

Consider a clique $$G=(V,E)$$ on $$n$$ vertices and any two distinct nodes $$s$$ and $$t$$.
Any permutation $$v_1, v_2, \dots, v_{n-2}$$ of the vertices in $$V \setminus \{s,t\}$$ induces a simple path from $$s$$ to $$t$$, namely $$\langle s, v_1, v_2, \dots, v_{n-2}, t \rangle$$. Therefore the numebr of paths from $$s$$ to $$t$$ is at least: $$(n-2)! = \Omega\left(\sqrt{n} \cdot \left( \frac{n-2}{e}\right)^{n-2}\right) = \omega(2^n),$$ where we used Stirling's inequality and, for $$n \ge 14$$: $$\left( \frac{n-2}{e}\right)^{n-2}= 2^{(n-2) \log \frac{n-2}{e} } > 2^{(n-2) \log \frac{12}{3} } = 2^{2(n-2)} > 2^n.$$
As Pål GD points out, you can use an easier argument to get a weaker bound which is still enough for you needs. Fix an arbitrary order of vertices in $$V \setminus \{s,t\}$$ and notice that any subset $$X$$ of $$V \setminus \{s,t\}$$ induces a path from $$s$$ to $$t$$ that traverses the vertices in $$X$$ according the chosen order. Therefore there are at least $$2^{n-2} = \Omega(2^n)$$ paths from $$s$$ to $$t$$.