Results 1 to 4 of 4

Math Help - Bipartite graph problem

  1. #1
    Member
    Joined
    Oct 2007
    Posts
    159

    Bipartite graph problem

    I am suppose to come up with a formula for the number of edges in a bipartite graph with n vertices in one partition and and m vertices in the second partition. I need some help!!!!

    I am thinking that I would need to take 2^n and 2^m and then divide by something but I am not sure... Any guidance would be appreciated. Thank you all for caring about struggling math students!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,642
    Thanks
    1594
    Awards
    1
    Do you perhaps mean complete bipartite n \times m graph?
    Otherwise, there is no one formula, but a range of formulae.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2007
    Posts
    159

    Complete bipartite problem

    Yes, although the problem does not specify this the picture shown does have a title which states that it is a complete bipartite graph. So I need to come up with a formula for the number of edges in a complete bipartite graph with m vertices in one partition and n vertices in the other partition.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by Frostking View Post
    Yes, although the problem does not specify this the picture shown does have a title which states that it is a complete bipartite graph. So I need to come up with a formula for the number of edges in a complete bipartite graph with m vertices in one partition and n vertices in the other partition.


    Isnt it just mn? Each node in one of the partition can be connected to every node in the other. So the number of edges is mn.
    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, 05:47 AM
  2. complete bipartite subgraph of a graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 6th 2011, 05:13 PM
  3. Bipartite graph proof
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 2nd 2010, 11:47 AM
  4. Bipartite Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 14th 2010, 02:37 AM
  5. Bipartite Simple Graph
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 3rd 2009, 12:37 PM

Search Tags


/mathhelpforum @mathhelpforum