It’s been a long time on this blog and I can feel it through reduced traffic. But anyways, let me not worry about it and lets get to the point.
where denote the set of vertices of G.
Solution : A very important observation to make is this.
Claim 1 : Let VC be any vertex cover ( not necessarily minimum ) then the set V-VC will form an independent set and vice versa.
Proof : Let VC be a vertex cover. If V-VC does not form an independent set then there must be two vertices such that . But in that case VC can’t be a vertex cover as it did not cover (u,v).
For the other direction, let IS be an independent set. So V-IS must form a vertex cover. If not then there must be an edge, for which none of the incident vertex belong to V-IS. Then they must be in IS. It is a contradiction then that IS is an independent set.
Having established claim 1, it is easy to prove the original stated theorem. Let C be a minimum vertex cover ( for a graph, minimum vertex cover or maximum independent set need not be unique ). V-C must form an indepedent set. If V-C is not the maximum independent set then let I be the maximum independent set such that . From claim one there exist a vertex cover V-IS such that . But C was a minimum vertex cover and we found a smaller vertex cover V-IS. A contradiction! So the theorem holds :-).