Reply
Tue 13 Sep, 2005 07:47 pm
For this proof, I'm defining simple graphs to be graphs where no loops and no multiple edges are allowed between nodes. Then, I want to show that there are exactly 2^(n(n-1)/2) labelled simple graphs on n vertices. How do I go about doing this? Also, how many of these have exactly m edges? Thanks!
n(n-1)/2 is C(n,2), which is the number of ways of selecting two nodes, which is the number of possible edges.
Raising two to that power is the number of ways of selecting zero to n of those edges.
Take a look at binomial coefficients and Pascal's triangle.
markr wrote:n(n-1)/2 is C(n,2), which is the number of ways of selecting two nodes, which is the number of possible edges.
Raising two to that power is the number of ways of selecting zero to n of those edges.
Take a look at binomial coefficients and Pascal's triangle.
Is that a proof? I think we need to use induction on n to prove this result.
Sure. Why not?
If you MUST use induction, then show that it's true for n=1. Then, assuming it's true for n, calculate how many more graphs can be produced if one more node is added. Then, show that that is equal to 2^((n+1)(n+1-1)/2)
So, the proof you've given is a combinatorial one right? What does it have to do with Pascal's triangle. I don't see the connection. Also, how many of these have exactly m edges? Thanks!
Yes.
If you've got C(n,2) edges to choose from, how many ways can you select m of them? After you figure that out, check out the numbers in the C(n,2)th row of Pascal's triangle (and add them all up).
OK cool. I think I see it now. Thank you so much for the time and effort extended.
markr wrote:Yes.
If you've got C(n,2) edges to choose from, how many ways can you select m of them? After you figure that out, check out the numbers in the C(n,2)th row of Pascal's triangle (and add them all up).
OK. I'm confused again...
Can you please show me the whole thing for this part?
Thanks!
Are you familiar with permutations and combinations? Specifically, do you know how to calculate the number of ways of choosing r items from a set of n items?
In this case, you have C(n,2) (which is n*(n-1)/2) edges to choose from. How many ways can you choose 0, 1, 2, 3, etc edges from this set?
markr wrote:Are you familiar with permutations and combinations? Specifically, do you know how to calculate the number of ways of choosing r items from a set of n items?
In this case, you have C(n,2) (which is n*(n-1)/2) edges to choose from. How many ways can you choose 0, 1, 2, 3, etc edges from this set?
There are ( n(n-1)/2 choose m ) ways of selecting m edges from a set of n choose 2 edges.
Right?
Someone told me that it's 15 choose k.
Well, if n is 6 and you use 'k' instead of 'm', then it is C(15,k)
Stumble It!
Tweet This
Bookmark on Delicious
Share on Facebook
Share on MySpace