Why does a graph with n vertices have 2^n -2 cuts?

Question

Why does a graph with n vertices have 2^n -2 cuts? I can't figure this one out. With 4 vertices, I just cant get 14 cuts. I can get max. 12 cuts? What am I missing?

By cut , I mean V is divided into 2 pairs of non-empty vertex list- A and B.

Answer 1

A simple way to rationalize it, as well as enumerate the cuts, is to assign a binary digit for each node. A 0 indicates it's in set A and a 1 that it's in set B. Then simply increment, ignoring the case of 0 and 2^n - 1, leaving 2^n - 2 cuts. So, for a 4 vertex graph with vertices P,Q,R,S:

PQRS
0000 A : { P,Q,R,S } B : {} // ignore, B is empty
0001 A : { P,Q,R } B : { S }
0010 A : { P,Q,S } B : { R }
0011 A : { P,Q } B : { R,S }
0100 A : { P,R,S } B : { Q }
0101 A : { P,R } B : { Q,S }
0110 A : { P,S } B : { Q,R }
0111 A : { P } B : { Q,R,S }
1000 A : { Q,R,S } B : { P }
1001 A : { Q,R }, B : { P,S } 
1010 A : { Q,S } B : { P,R }
1011 A : { Q } B : { P,R,S }
1100 A : { R,S } B : { P,Q }
1101 A : { R } B : { P,Q,S }
1110 A : { S } B : { P,Q,R }
1111 A : {} B : { P,Q,R,S } // ignore, A empty

That leaves you 14, 2^4 - 2.