Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Complete Bipartite Graphs

  1. Apr 21, 2012 #1
    1. The problem statement, all variables and given/known data
    How many complete bipartite graphs have n vertices?

    2. Relevant equations

    3. The attempt at a solution
    I said, let the first bipartition set have x vertices and the second bipartition set have y vertices. So x+y=n.

    I think that you would do C(n, x)*C(n-x, y)=C(n,x)*C(y,y)=C(n,x) but I feel like this is either wrong or not good since I made x and y up arbitrarily.

  2. jcsd
  3. Apr 21, 2012 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    So that's the number of complete bipartite graphs with the "first" partition having size x. What are the possible values for x?
  4. Apr 21, 2012 #3
    There are n possible values for x... so is the answer n*C(n,x)?

    Is there any problem with me having made x up without it being in the problem?

    Also, would I instead want to do something like C(x,1)*C(y,1) [to get the number of ways to pick the vertices] *C(n,x) [to get the number of ways of making the 'first' bipartition set] *n?
  5. Apr 22, 2012 #4
    Could it matter if there is an even/odd number of vertices in any one bipartition set?
  6. Apr 22, 2012 #5
    Any new ideas?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook