Number of mincuts of a graph without using Karger's algorithm

Question

We know that Karger's mincut algorithm can be used to prove (in a non-constructive way) that the maximum number of possible mincuts a graph can have is $n \choose 2$.

I was wondering if we could somehow prove this identity by giving a bijective (rather injective) proof from the set of mincuts to another set of cardinality $n \choose 2$. No specific reasons, its just a curiosity. I tried doing it on my own but so far have not had any success. I would not want anyone to squander time over this and so if the question seems pointless I would request the moderators to take action accordingly.

Best -Akash

Answer 1

The $\binom{n}{2}$ bound I think was originally proven by Dinitz, Karzanov and Lomonosov in 1976, in "A structure for the system of all minimum cuts of a graph". Perhaps you can find what you're looking for in this paper, but I'm not sure if it's online.

Answer 2

Informally, one can argue that in order to have the maximum number of min-cuts, all nodes in a graph must have the same degree.

Let a cut divide a graph $G$ into two set of nodes $C$ and $\bar C$ such that $C \cap \bar C=\emptyset$. Let the number of min-cuts in a graph be denoted as $mc(G)$.

Consider a connected graph with $n$ vertices in which each vertex has degree two. This must be the cycle graph and the minimum cut is two edges. It is obvious that cutting any two edges will result in a cut and that such a cut is a minimum cut. Since there are $n(n-1)/2$ distinct pairs of edges there are $n(n-1)/2$ minimum cuts.

Make a new graph by removing an edge from the cycle graph. The minimum cut of the new graph is one edge and cutting any edge will suffice: there are $n-1$ such cuts which can be made.

Make a new graph by adding an edge to the cycle graph. Now two nodes have degree three and $n-2$ nodes have degree two. The degree three nodes must both belong to $C$ or both belong to $\bar C$. Note that in the case of the cycle graph, no nodes were restricted to appear together in $C$ or $\bar C$. The implication is that adding an edge adds a constraint, which reduces the number of minimum cuts.

Promoting more nodes to degree three adds additional constraints up until the point where there is only one minimal cut of degree two.

The foregoing shows that the cycle graph is (at least) a local maximum of $mc$.

Consider the set of graphs in which every node is of degree three. Removing an edge yields a graph with a single min-cut of two. Adding an edge, as above, produces two nodes that most appear on the same side of the cut.

This suggests that the graphs in which every node is of degree $k$ are local maxima of $mc$. Noting that the complete graph has $mc=n$ cuts of size $n-1$ suggests that this is a declining function.

I haven't put too much thought into whether it is possible to formalize the above, but it represents a possible approach.

Also, I think the Bixby paper Jelani Nelson mentions in the comment to his answer is entitled "The Minimum Number Of Edges And Vertices in A Graph With Edge Connectivity n And M n-bonds" (link)