# 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. – Tsuyoshi Ito Feb 4 '13 at 22:11
• Please define $\omega(n)$. – Yoshio Okamoto Feb 4 '13 at 23:18
• @YoshioOkamoto It is probably some function that asymptotically dominates the linear function. What else could it be? – Pål GD Feb 5 '13 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. – Frumple Feb 5 '13 at 20:56
• Please write all the conditions in the question (even if they are not rigorously defined). – Tsuyoshi Ito Feb 6 '13 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.