A problem in graph theory


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

|I| + |C| = |V| where V 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 u,v \in V-VC such that (u,v) \in E. 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 |IS| > |V-C|.  From claim one there exist a vertex cover V-IS such that |V-IS| < |C| . But C was a minimum vertex cover and we found a smaller vertex cover V-IS. A contradiction! So the theorem holds :-).

–Saurabh Joshi


Tags: , ,

3 Responses to “A problem in graph theory”

  1. Marius Says:

    Notice a similar approach:

  2. Ranganath Says:

    Hello Saurabh,

    Your blog is really fantastic 🙂 I really liked many of the puzzles/questions here.

    Good work,

    Thanks for sharing the knowledge.

  3. connect2ppl Says:

    one more observation : since C forms Min VC, it implies that for every vertex v belonging to C there exists an edge e incident on it , and the other end of edge e belonging to V-C ( if there is no such edge, v can be safely removed from C and still have VC, contradicting the assumption that C is Min VC )

    Using above and the fact that V-VC is IS, we can conclude that V-C is Max IS.
    The way i proved needs above observation, my proof is Direct in nature.

    Lesson Learnt : Proof by contradiction ( Saurabh used this ) lets you to SAFELY overlook some observations.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: