14
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Kumar, an $n$-vertex clique has $n$ mincuts, separating each vertex from the rest of the graph, so the number of mincuts may be less than $n\choose 2$. $\endgroup$ – Marcus Ritt Nov 25 '10 at 22:58
  • 2
    $\begingroup$ This is a very accessable note on proving this combinatorially. cs.elte.hu/egres/qp/egresqp-09-03.ps $\endgroup$ – Chao Xu Mar 6 '16 at 7:58
10
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks jelani....tried looking up the paper online. No luck so far. I think I will try my college's library. In the meanwhile, if you find time (and are up for it) could you try highlighting some of the key ideas of the paper? It would be great if you could. Thanks again! $\endgroup$ – Akash Kumar Nov 26 '10 at 1:57
  • 1
    $\begingroup$ Sorry, I don't know how their proof works. :/ Apparently there might have been an earlier proof implied some work of Robert Bixby. You'll probably be able to find out more than I know via some Googling (or maybe someone who knows more can provide a better answer here). I'm curious to hear the answer myself ...I remember once wondering about this same question back when I first learned Karger's algorithm. $\endgroup$ – Jelani Nelson Nov 26 '10 at 2:43
2
$\begingroup$

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)

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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