Number of Complete Bipartite Graphs with n Vertices

  • Thread starter Thread starter schaefera
  • Start date Start date
  • Tags Tags
    Complete Graphs
Click For Summary

Homework Help Overview

The discussion revolves around determining the number of complete bipartite graphs that can be formed with a total of n vertices. The problem involves understanding the structure of bipartite graphs and how to partition the vertices into two sets.

Discussion Character

  • Exploratory, Assumption checking, Problem interpretation

Approaches and Questions Raised

  • Participants explore the idea of partitioning n vertices into two sets, x and y, and question the validity of their arbitrary choices for x and y. They discuss the implications of different values for x and whether the parity of the vertex count in the bipartition sets matters.

Discussion Status

The discussion is ongoing, with participants raising questions about the assumptions made in their attempts. Some guidance has been offered regarding the number of possible values for x, but there is no explicit consensus on the correct approach or formula yet.

Contextual Notes

Participants express uncertainty about whether their arbitrary choices for x and y are valid within the context of the problem. There is also a consideration of how the evenness or oddness of the vertex counts in the bipartition sets might affect the outcome.

schaefera
Messages
208
Reaction score
0

Homework Statement


How many complete bipartite graphs have n vertices?


Homework Equations





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?
 
Physics news on Phys.org
So that's the number of complete bipartite graphs with the "first" partition having size x. What are the possible values for x?
 
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?
 
Could it matter if there is an even/odd number of vertices in anyone bipartition set?
 
Any new ideas?
 

Similar threads

Replies
3
Views
2K
  • · Replies 9 ·
Replies
9
Views
2K
  • · Replies 2 ·
Replies
2
Views
3K
Replies
20
Views
4K
  • · Replies 4 ·
Replies
4
Views
8K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 3 ·
Replies
3
Views
2K
Replies
2
Views
1K
Replies
9
Views
3K
  • · Replies 2 ·
Replies
2
Views
3K