1 00:00:00,000 --> 00:00:05,530 So the answer to this first question is k and that's because--well, we've already gotten rid 2 00:00:05,530 --> 00:00:10,790 of any vertices that have k+1 edges or more, so all the remaining vertices 3 00:00:10,790 --> 00:00:13,840 can have at most k edges connected to them. 4 00:00:13,840 --> 00:00:19,230 Now, to answer this final problem, we have to remember that we said earlier 5 00:00:19,230 --> 00:00:24,900 that at most k vertices are needed to cover the entire graph. 6 00:00:24,900 --> 00:00:31,800 Well, if there are k vertices necessary to cover the graph and each vertex has at most 7 00:00:31,800 --> 00:00:37,920 k edges attached to it, then the remaining graph can have no more than 8 00:00:37,920 --> 00:00:41,240 k² edges since we have to cover all of them. 9 00:00:41,240 --> 00:00:46,040 Now, this might have seem that we were involved, but there's actually something powerful here. 10 00:00:46,040 --> 00:00:51,600 What this means is that after doing all of these little pre-processing steps, then we either know 11 00:00:51,600 --> 00:00:57,800 that the graph G is not a "Yes" instance of the vertex cover decision problem-- 12 00:00:57,800 --> 00:01:04,200 in other words, it's a "No" instance or we know that the size of the resulting graph is bounded 13 00:01:04,200 --> 00:01:09,800 not as a function of n, which it was originally, but rather as a function of k, 14 00:01:09,800 --> 00:01:15,460 and remember what we said earlier that very often k is far less than n. 15 00:01:15,460 --> 99:59:59,999 So this is potentially a very big win for us.