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