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).