1) choose k
2) repeat k times:
  3) choose random i, j in [1,n]
  4) if there is an edge (i,j), goto 3
  5) add edge (i,j)