I am trying to find the solution to this problem :

How many cuts does a graph with n vertices have ?

Definition of cuts : https://en.wikipedia.org/wiki/Cut_(graph_theory)

I actually converted this question into an equivalent problem :

In how many ways can I put n distinct balls in two baskets (distinct) such that none of the baskets is empty? (Assuming each basket can hold infinite balls).

Firstly, I want to confirm that this is a correct equivalent problem.

Secondly, I tried to solve this problem in the following way:

Since we have two baskets and we can fill each basket in n ways, hence each total ways = $n^2$ and from this we subtract two cases which correspond to each basket being empty.

But I checked the correct solution to this problem is $2^n - 2$. Intuitively I can figure out after looking at the solution that since each ball has two ways to go in the basket (either A or B), hence total ways are $2^n$, but I am unable to figure out -

Why is my first approach incorrect? (I am unable to develop an intuition as to why my first approach is incorrect).

  • 1
    $\begingroup$ You have to put all the balls in the two baskets, so once you decide what is in the first, the rest goes in the second basket (only 1 possibility). For the first basket, you won't have only $n$ possibility, since all the balls are differents. You have $n$ possibility of having 1 ball in the first basket. $\binom{n}{2} = \frac{n(n-1)}{2}$ possibility of having 2 balls in the first basket, and so on. $\endgroup$ – Alain Remillard Oct 28 '15 at 22:02

I am able to solve the problem using the first approach. But there was a fundamental error in the first approach which was hinted by @Alian Remillard in the comments.

Here is the answer through first approach: We have two baskets say, A and B and n balls.
Now these are the possible configurations : $(n,0), (n-1,1) , (n-2,2) , .... , (0,n)$ , where $(x,y)$ means that x balls go into basket A, and y balls go to basket B.

Hence total number of ways = ${n \choose n} + {n \choose n-1} + .... + {n \choose 0} = 2^n$. For each (x,y), there will be $n \choose x$ cases as we have to fundamentally choose x balls from n balls and place them in basket A, rest go in basket B. Note that we can do the reverse also , i.e, ${n \choose y}$ which is the same as ${n \choose x}$ as $x+y=n$.

From this we can subtract two cases in which either of the baskets is empty. Hence final answer is $2^n - 2$


First, I am not sure that the question

In how many ways can I put n distinct balls in two baskets (distinct) such that none of the baskets is empty? (Assuming each basket can hold infinite balls).

Is equivalent to the one asked: a cut can be defined as the minimal set of edges necessary to disconnect a set $V_0\in V$ from the rest of the graph. Often you write a cut as $\delta(V_0)$. Thinking in this way you can think at the problem :

Given a set of elements $V$, how many ways are there to ripartite all the elements in two sets?

This is not enough because you can easy prove that $\delta(V_0)= \delta(V \setminus V_0)$.

So the problem you asked is equivalent to

Given a set of balls and two indistinguishable baskets , how many distinguishable ways are there to distribute all the balls into the two baskets, such that none of the baskets is empty?

The solution is $\frac{2^n-2}{2}=2^{n-1}-1$

Proof: The number of different binary strings of length $n$, it is $2^n$. For each string $S$ consider the configuration where: the $i^th$ ball is assigned to the basket A if $S_i=0$ and it is assigned to basket B otherwise.

There are two inadmissible configuration: the strings made all of ones and the string made all of zeroes (in this cases one of the two baskets is empty).

To conclude we notice that whe have to divide by 2 because we can switch basket A and B.



Your Answer

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