Tight Lower Bounds for the Number of Inclusion-Minimal st-Cuts

We study the number of inclusion-minimal cuts in an undirected connected graph G, also called {\$}{\$}st{\$}{\$}st-cuts, for any two distinct nodes s and t: the {\$}{\$}st{\$}{\$}st-cuts are in one-to-one correspondence with the partitions {\$}{\$}S {\backslash}cup T{\$}{\$}S∪Tof the nodes of G such that {\$}{\$}S {\backslash}cap T = {\backslash}emptyset {\$}{\$}S∩T=∅, {\$}{\$}s {\backslash}in S{\$}{\$}s∈S, {\$}{\$}t {\backslash}in T{\$}{\$}t∈T, and the subgraphs induced by S and T are connected. It is easy to find an exponential upper bound to the number of {\$}{\$}st{\$}{\$}st-cuts (e.g. if G is a clique) and a constant lower bound. We prove that there is a more interesting lower bound on this number, namely, {\$}{\$}{\backslash}varOmega (m){\$}{\$}$\Omega$(m), for undirected m-edge graphs that are biconnected or triconnected (2- or 3-node-connected). The wheel graphs show that this lower bound is the best possible asymptotically.