Deleting edges from complete graph

I have a complete undirected graph with $V$ vertices and $\frac{V(V - 1)}{2}$ edges. Then, I remove $K$ edges $(a_i, b_i)$. I want to know if the graph is still connected after performing all the operations (so I want to delete those edges and then answer the question). Is there any faster way to do this than performing BFS/DFS algorithm? Those are linear time algorithms but in terms of edges which may be quite big to compute on a home PC for graphs with approximately $10^6$ vertices. $K$ of course will not be too big, let's say up to $10^6$.

• Have you tried proving a lower bound? What happens if you can not inspect all edges? – Raphael Oct 11 '16 at 6:41
• Related posts: this, this, this, this. Duplicate? – Raphael Oct 11 '16 at 6:45
• None of them are helpful or related – user128409235 Oct 11 '16 at 11:15
• In which way are they not related? #1 and #4 seem to deal with a generalization of your problem! – Raphael Oct 11 '16 at 12:09
• The links Raphael provided indeed solve generalisations of your problem. Do some work yourself and read them. – j_random_hacker Oct 11 '16 at 12:34

To disconnect a complet graph $G=(V,E)$ into $V_1,V_2$ you have to remove at least $|V_1|*|V_2|$ edges (all the edges between elements of $V_1$ and elements of $V_2$).
Thus if $K<m*(|V|-m)$ you are sure that either the resulting graph is connected or there is a set of vertices $V_1$ such that $|V_1|<m$ which is disconnected.
Hence to check if your graph is connected you only need to check whether each vertex is connected to at least $m$ vertices. Thus you have to check only $m*|V|$ edges, which is better than BFS depending on $m$ (hence on $|K|$)