So the answer to this first question is k and that's because--well, we've already gotten rid
of any vertices that have k+1 edges or more, so all the remaining vertices
can have at most k edges connected to them.
Now, to answer this final problem, we have to remember that we said earlier
that at most k vertices are needed to cover the entire graph.
Well, if there are k vertices necessary to cover the graph and each vertex has at most
k edges attached to it, then the remaining graph can have no more than
k² edges since we have to cover all of them.
Now, this might have seem that we were involved, but there's actually something powerful here.
What this means is that after doing all of these little pre-processing steps, then we either know
that the graph G is not a "Yes" instance of the vertex cover decision problem--
in other words, it's a "No" instance or we know that the size of the resulting graph is bounded
not as a function of n, which it was originally, but rather as a function of k,
and remember what we said earlier that very often k is far less than n.
So this is potentially a very big win for us.