
Let's build off this a little bit.

Let's do that by taking all of these vertices that have k+1 edges or more and actually putting them

in the cover and that's because we already said it has to be in the cover.

Now, what we can do is actually remove these vertices from the graph and any edges

connected to them because those edges are automatically covered

so we don't have to worry about them anymore.

We automatically are dealing with a much smaller graph or potentially much smaller graph.

What this tells us is that after removing these vertices, each remaining vertex can cover

at most a certain number of edges if it's put in a cover, and this could either be

k1, k, k+1, 2k, or k² edges.

What this would then mean is that the remaining graph can't have no more than a

certain number of edges if G is a "Yes" instance of the vertex cover decision problem,

which is the original assumption that we made, and this can either be k1, k, k+1, 2k, or k².

So please check whichever is appropriate for both of these questions.