Given a graph $(V, E)$ and a pair of vertices $u$ and $v$, a minimal $(u,v)$ cut-set is a subset $S\subseteq V$ such that in $G-S$ there is no path between those vertices.
I want to know if there is a polynomial upper bound to the number of such sets for a fixed pair. Well, I know that $n\choose{n/2}$ is an upper bound since such family of sets has the Sperner property. However, I am not able to construct a graph that has the number of minimal cut-sets near this bound.
Unless I'm misreading something, how about the following simple example to show there is no polynomial upper bound: suppose that $u$ and $v$ are connected via $\sqrt{n}$ disjoint, linear paths consisting of $\sqrt{n}$ vertices each. Then for each choice of a single node on each path, we get a distinct minimal $(u,v)$ cut-set. This gives $n^{\sqrt{n}/2}$ such sets, which is not polynomial, though not as bad as your upper bound (the logarithm of this construction scales like $\sqrt{n}\log n$ while your bound scales like $n$ asymptotically).