Results 1 to 4 of 4

Thread: 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
    21,742
    Thanks
    2814
    Awards
    1
    Do you perhaps mean complete bipartite $\displaystyle 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 $\displaystyle mn$? Each node in one of the partition can be connected to every node in the other. So the number of edges is $\displaystyle 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: Mar 10th 2012, 05:47 AM
  2. complete bipartite subgraph of a graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Sep 6th 2011, 05:13 PM
  3. Bipartite graph proof
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Nov 2nd 2010, 11:47 AM
  4. Bipartite Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Oct 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