# Homework Help: Complete Bipartite Graphs

1. Apr 21, 2012

### schaefera

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.

Help?

2. Apr 21, 2012

### Office_Shredder

Staff Emeritus
So that's the number of complete bipartite graphs with the "first" partition having size x. What are the possible values for x?

3. Apr 21, 2012

### schaefera

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?

4. Apr 22, 2012

### schaefera

Could it matter if there is an even/odd number of vertices in any one bipartition set?

5. Apr 22, 2012

### schaefera

Any new ideas?