[r0uv3n]

I guess you can just add some edges extra vertices and edges and give all the extra edges probability 1 of being deleted.