Ahmed_Hussein_Karam's blog

Graph theory
By Ahmed_Hussein_Karam, history, 8 years ago, In English

According to this wikipedia link, under the title "Success probability of the contraction algorithm":
Number of possible cuts in a graph is 2^(n-1)-1, while maximum number of minimum cuts is nC2, where n is number of vertices.
My question:
Why number of possible cuts differ from maximum number of minimum cuts? why isn't any cut a (candidate) minimum cut?

  • Vote: I like it
  • +6
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Why did people downvote his post? He's just asking a question!

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    as much as I agree that people should not downvote this post, why did people upvote his post? He's just asking a question!

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      i din't read his blog but some people thinks his question is good so they upvoted him.

      // some people thinks ? or think ?

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        I agree. Point is so you upvote if you thinks the question is good. Can't you downvote if you think the question is bad?

        → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I really wonder, why are all upvotes are given to all of these useless comments and almost no one tried to upvote the below answer that really was helpful and solved the problem?
      If you think that I am asking the question just to be upvoted or downvoted, then you must have misunderstood.
      That is, I can seek for upvotes by publishing a nice photo on a contest announcment blog or something similar, but how on earth can I seek such votes by making up a critical question in Graph Theory?! Which is easier?!

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        I didn't say that you are. I am just tired of seeing how people control what should be upvoted and downvoted and what should not be(because I think sometimes people ask question just to solve their own problem without thinking long enough deserved to be downvoted) (clearly not this blog), and hence my comment. If you think my comment is specifically towards you, I am sorry.

        I think the reason the comment below did not get much upvote is because it is too long, not many people understands it and probably people are not interested in the proof. I generally do not upvote something I don't understand just in case what he say is wrong.

        → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

Not a formal proof, but an attempt.

For N <= 3 : nC2 = 2n-1 - 1

For N >= 4: We will prove by contradiction. Let all the possible 2n-1 - 1 cuts be a minimum cut.

Consider a case: We have a graph G = (V,E), Let V = {1,2,...N}, N >= 4

Consider a cut with the disjoint sets S,_T_. Since a cut will have all the possible combinations of S and T such that S U T = V and S and T are disjoint.

Let S = {1}, T = {2,3....N} and the condition that 1 is connected to atleast one vertex of T, otherwise we will have a trivial graph.

Since we are saying that all cuts are minimum cut, this cut is also a minimum cut.

Now, transfer one vertex from T to S. The moved vertex, say i, is connected to 1 (as we assumed earlier, atleast one vertex of T is connected to 1). Since the resulting cut after the movement should also be a minimum cut, the moved vertex should have the same number of neighbours in T as well in S(one here). So, we get a case that 1 is connected to all the nodes in T, since we can attempt to move every vertex in set T.

Now, consider S = {2}, T = {1,3,4..N}.

Let this be a minimum cut (since we assumed all cuts are minimum cuts), try moving 1 from T to S, but we have atleast two neighbours of 1 in T (N>=4 and 1 is connected to all nodes), but one neighbour in S. So, the number of removed edges in the current cut is less than the number of removed edges in the set we will obtain after moving 1 from T to S.

So, both of them cannot be minimum cut.

So, there are always cuts in a graph, that is not a minimum cut.

Please do correct me if I'm wrong.

→ Reply