MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Among all graphs with $n$ vertices and edge-connectivity exactly $c$ (so the size of the minimum edge cut is $c$), there is a well-known result of Lomonsov and Poleskkii that the cycle graph, which consists of $n$ vertices arranged in a cycle, and $c/2$ parallel edges between adjacent vertices, has the fewest MINIMAL cuts (i.e. cuts of weight exactly c)

What happens if $c$ is odd? Strangely, all the references I can find to this result omit this case.

EDIT: I left out the condition that the graph has the fewest MINIMAL cuts. Sorry.

share|cite|improve this question
you are writing fewest minimal cuts, which usually stands for inclusion minimal, but then you say that you mean cuts of weight $c$, which are usually called minimum cuts, and are a subset of the miimal cuts. It is very easy to construct graphs with only one minimum cut, so this can not be what you are looking for. For minimal cuts, my answer below still works. Maybe there is yet another condition on the graphs? – Flo Pfender Mar 31 '12 at 6:18
up vote 1 down vote accepted

Maybe, I don't quite understand the question, but the answer appears to be a very similar graph:

Take the graph that you are looking for. Now double up certain edges until your smallest cut has size $c+1$. This will not change the number of cuts, as doubling edges does not change this number. Now Lomonosov and Poleskii (I could not look at their article) tell you a lower bound for the number of cuts of that new graph.

On the other hand, take the cycle graph with $(c+1)/2$ parallel edges between adjacent vertices, and delete one edge. This graph (assuming $c>1$) has the same number of cuts as the cycle graph, and edge connectivity exactly $c$.

If you are instead asking for a graph where every minimal cut has size $c$, then this is not the answer...

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.