# Thread: Bipartite graph problem

1. ## 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!

2. Do you perhaps mean complete bipartite $n \times m$ graph?
Otherwise, there is no one formula, but a range of formulae.

3. ## 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.

4. Originally Posted by Frostking
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$.