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.



Least reliable graph when edge-connectivity is odd
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...


