Contract random edges until two super-vertices are left: the edges between them are a cut. One trial is often wrong, so run many and keep the smallest.
This interactive visualization needs JavaScript.