A problem in graph theory

Well,

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.

The problem was brought to me by manoj for which saket gave a very elegant and simple solution. Me and satyam made some good observtions but not the one which matterred the most :-).

Problem : Let G be any undirected graph. Let I be the maximum independent set and C be the minimum vertex cover for this graph.  Prove that

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 :-).

–Saurabh Joshi