I have a solution that I cannot prove whether it is true or not. However it passed all the final tests. See my code here 4635501

1. Pick up 1 unmarked vertice w and 2 marked vertices u & v. The rest vertices are in the set V0.
2. Add edge between vertices {w + v + V0} to form a complete undirected graph.
3. Add edge between vertices w & u.
4. Add edge between vertices u & all vertices in set S which are unmarked.

The maximum number of edges is (n-1)*(n-2)/2+1+(n-k-1).