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.