So now, let's do our best to mimic the argument in case one.

In case one, we said well, S has to also be an independent set of G

prime. Now, here that doesn't make sense, right?

Here, S contains the last vertex so we can't talk about it even being a subset

of any smaller graph. However, if we think about S except for

the last vertex of V sub n, S with Vn removed is an independent set, in fact,

of G double prime, because remember, S can't contain the second to last vertex.

And once again, just like in case one we can say something stronger, S with Vn

removed is not any old independent set of G double prime, it actually must be an

optimal one. It must have maximum possible weight. The

reasoning is similar. Suppose S with Vn removed was not the best possible

independent set in G double prime. Then there's something else called an S

star which is even better, has even bigger weight.

How do we get a contradiction? Well, if we just add Vn to this even

bigger independent set S star that lies in G double prime, we get a bonafide

independent set of the entire graph G with overall weight even bigger than that

of S, but that contradicts the optimality of S.

So, for example you could imagine that this reported optimal solution capital S

had total weight 1,100 in two parts, it had 1,000 weight coming from vertices in

the G double prime, but it also had V sub n which had weight 100 on its own. And so

now, in the contradiction, you say, well, suppose there was an independent set that

had even more than 1,000 weight just in G double prime, say, 1,000 and 50.

Well then, we just add this last vertex V sub n to that, we get an independent set

with weight 1,150 and the original graph G.

But that contradicts the fact that S was supposed to be off more with weight

nearly 1,100. So, notice that the reason were using the

graph G double prime in this argument is to make sure that no matter what S star

is, no matter what this independent set of G

double prime is. We can just add V into it blively and not

worry about feasibility, right?

So, the right-most vertex S star could possibly possess is the third to last

vertex Vn - 2. So, there's no worries about feasibility

when we extend it by adding in the right-most vertex V sub n.