Results 1 to 2 of 2

Math Help - Bipartite Graph

  1. #1
    Super Member
    Joined
    Feb 2008
    Posts
    535

    Bipartite Graph

    Let G be a bipartite graph. Prove that alpha (G) = n(G)/2 if and only if G has a perfect
    matching.

    Let alpha(G) = max size of an independent set of vertices
    Let n(G) = the order of G

    Any thoughts? Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162
    Here is an outline of the proof. Try to fill up the details:

    If G has a perfect matching, then its bipartition consists of two vertex sets A and B with equal cardinality. Choosing all the vertices of any one of these sets gives us the maximum independent set. If there exists a bigger independent set of at least n/2+1 vertices then we can use pigeonhole principle over it and the n/2 edges of the perfect matching to arrive at a contradiction.


    Now let G contain a maximum independent set of size n/2. If there is such an independent set having vertices from both the A and B, then we can use induction. Otherwise, wlog consider the maximum independent set A. Now we can show that if for some subset A' of A defies Hall's condition, then A - A' will have a set of neighbours n(A-A') in B such that |n(A-A')| > |A-A'|, and obviously |n(A-A')| is disjoint from the neighbours of A'. From here we can obtain a bigger independent set.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph theory, bipartite Graph
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: March 10th 2012, 06:47 AM
  2. complete bipartite subgraph of a graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 6th 2011, 06:13 PM
  3. Bipartite graph proof
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 2nd 2010, 12:47 PM
  4. Bipartite Simple Graph
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 3rd 2009, 01:37 PM
  5. Bipartite graph problem
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 11th 2008, 11:54 PM

Search Tags


/mathhelpforum @mathhelpforum