<p>Aside from the cycle graph, I think a nontrivial class of graphs with $\Omega(n^2)$ 
distinct min cuts are cactuses. A <em>cactus</em>  is a connected graph in which every block (a maximal 2-connected subgraph) is a chordless cycle. </p>

<p><strong>EDIT</strong>: 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)$, 
<em>provided</em> the number of blocks $b$ is bounded.</p>

CC BY-SA 3.0
2013-02-09T09:41:14.837Z
We need to restrict to leaf-free graphs at least. The number of minimum cuts is then the sum of the number of minimum cuts in each block (i.e. cycle). This can be linear, for example if the maximum of the orders of the blocks is bounded.
Colin McQuillan
CC BY-SA 3.0
2013-02-09T14:17:03.873Z
@ColinMcQuillan: By definition, cactuses have no leaves. And you are right! I overlooked the case of bounded cycle lengths. Thank you for your comments. I have edited it accordingly.
user13136
CC BY-SA 3.0
2013-02-08T18:25:55.630Z
2013-02-09T14:16:16.293Z
2013-02-09T14:16:16.293Z
user13136
<p>Aside from the cycle graph, are there other simple unweighted graph constructions for which there are $\omega(n)$ distinct min cuts?</p>

CC BY-SA 3.0
2013-02-04T22:11:34.093Z
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
CC BY-SA 3.0
2013-02-04T23:18:26.187Z
Please define $\omega(n)$.
Yoshio Okamoto
CC BY-SA 3.0
2013-02-05T12:02:57.447Z
@YoshioOkamoto It is probably some function that asymptotically dominates the linear function.  What else could it be?
John K.
CC BY-SA 3.0
2013-02-05T20:56:44.073Z
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
CC BY-SA 3.0
2013-02-06T04:15:13.887Z
Please write all the conditions in the question (even if they are not rigorously defined).
Tsuyoshi Ito
<graph-theory>
Graphs for maximum number of min cuts?
Frumple
# Graphs for maximum number of min cuts?

(Asked by: username_0 on 2013-02-04)

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

**Tags:** graph-theory
> **Comments:**
> **username_1**: 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.  
> **username_2**: Please define $\omega(n)$.  
> **username_3**: @YoshioOkamoto It is probably some function that asymptotically dominates the linear function.  What else could it be?  
> **username_0**: 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.  
> **username_1**: Please write all the conditions in the question (even if they are not rigorously defined).  

---

## 1 answers

### Answer by username_4 on 2013-02-08. Score: 8

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.

> **Comments:**
> **username_5**: We need to restrict to leaf-free graphs at least. The number of minimum cuts is then the sum of the number of minimum cuts in each block (i.e. cycle). This can be linear, for example if the maximum of the orders of the blocks is bounded.  
> **username_4**: @ColinMcQuillan: By definition, cactuses have no leaves. And you are right! I overlooked the case of bounded cycle lengths. Thank you for your comments. I have edited it accordingly.  

---

