Graph theory

Revision en2, by Ahmed_Hussein_Karam, 2017-06-06 00:43:43

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?


  Rev. Lang. By When Δ Comment
en2 English Ahmed_Hussein_Karam 2017-06-06 00:43:43 10 Tiny change: 'is 2^(n-1) — 1, while m' -> 'is 2^(n-1)-1, while m'
en1 English Ahmed_Hussein_Karam 2017-06-06 00:43:03 486 Initial revision (published)