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.