# Graphs for maximum number of min cuts?

Aside from the cycle graph, are there other simple unweighted graph constructions for which there are $\omega(n)$ distinct min cuts?

• There are: the graphs with no edges have exponentially many distinct minimum cuts (trivially). If you want a connected graph, how about adding one chord to a cycle? It still has Θ(n^2) distinct minimum cuts. I am not sure if these are what you are looking for, though. Commented Feb 4, 2013 at 22:11
• Please define $\omega(n)$. Commented Feb 4, 2013 at 23:18
• @YoshioOkamoto It is probably some function that asymptotically dominates the linear function. What else could it be? Commented Feb 5, 2013 at 12:02
• Sorry, I should have been more clear. By $\omega(n)$, I mean the number of min cuts is superlinear in the number of nodes $n$. With the chord idea, I suppose it's easy enough to start with a cycle graph and "pare down" the number of min cuts to be whatever you like. I was hoping though, that there was some other easy examples of connected graphs with large numbers of min cuts which were somehow structured differently than the cycle graph. Commented Feb 5, 2013 at 20:56
• Please write all the conditions in the question (even if they are not rigorously defined). Commented Feb 6, 2013 at 4:15

Aside from the cycle graph, I think a nontrivial class of graphs with $\Omega(n^2)$ distinct min cuts are cactuses. A cactus is a connected graph in which every block (a maximal 2-connected subgraph) is a chordless cycle.
EDIT: In case the considered cactus has $n$ nodes and $b$ blocks of order $n_1, n_2, \ldots, n_b$, the number of min cuts is $\Omega\left(\sum_{i=1}^b n_i^2\right)$. As $\sum_{i=1}^b n_i^2 \ge \frac{1}{b} n^2$, the number of min cuts is $\Omega(n^2)$, provided the number of blocks $b$ is bounded.