Randomize
Repeat until 2 vertices remain
pick a random edge
contract it
(keep fingers crossed)