-An edge between any two given vertices exists with probability p -Create new edges until graph is connected
