My Math Forum Graph Theory - Simple Labelled Graphs

 Applied Math Applied Math Forum

 May 13th, 2013, 01:16 PM #1 Senior Member   Joined: Jan 2012 Posts: 118 Thanks: 1 Graph Theory - Simple Labelled Graphs Hello! Not sure which section to post this in so I'll just post it here for now. Have this question to answer in my Graph Theory class.... a. Show there are exactly $2^{\frac{n(n-1)}{2}}$ labelled simple graphs of order n My teacher mentioned that it is possible to do this by induction... so I showed the base case which was true. And then didn't know where to go once I tried proving that this equation was true: $2^{\frac{k(k+1)}{2}}= 2^{\frac{k(k-1)}{2}}$ I just don't see how we can ever make these two sides equal. It doesn't neessarily have to be solved by induction, so any help would be great. b. How many of these have exactly m edges? With this one I have no clue where to start... what does m even equal in this situation?
May 13th, 2013, 06:56 PM   #2
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Graph Theory - Simple Labelled Graphs

Quote:
 Originally Posted by Jet1045 And then didn't know where to go once I tried proving that this equation was true: $2^{\frac{k(k+1)}{2}}= 2^{\frac{k(k-1)}{2}}$ I just don't see how we can ever make these two sides equal.
They aren't.

What you want is to look at 2^(n(n+1)/2) / 2^(n(n-1)/2) = 2^n. This is how many times more graphs of size n+1 there are than of size n. Now you get a graph of size n+1 from a graph of size n by adding in one new (labeled) point and choosing which edges to add... can you see why this is 2^n?

 May 13th, 2013, 07:35 PM #3 Senior Member   Joined: Jan 2012 Posts: 118 Thanks: 1 Re: Graph Theory - Simple Labelled Graphs Hmmm, do you end up with 2^n after you simplify that expression of 2^(n(n+1)/2) / 2^(n(n-1)/2)? I kind of see what you are saying... so would I be able to use this approach while using induction? Like to do just divide both sides by 2^(n(n-1)/2)? and then simplify to get 2^n? Or did you intuitively know where to go when you consider the case n+1?
May 13th, 2013, 08:45 PM   #4
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Graph Theory - Simple Labelled Graphs

Quote:
 Originally Posted by Jet1045 Hmmm, do you end up with 2^n after you simplify that expression of 2^(n(n+1)/2) / 2^(n(n-1)/2)?
Well, it's obvious -- isn't it? -- that the result will be 2^(n(n+1)/2 - n(n-1)/2). Do the subtraction and see what you get. I'm certainly not immune to arithmetic mistakes.

Quote:
 Originally Posted by Jet1045 I kind of see what you are saying... so would I be able to use this approach while using induction?
It *is* induction -- I assumed the result on n points and derived the result on n+1 points. But don't take my word for it, prove it! How many new edges can there be when connecting a point to each of n other points? How many ways can you choose to make or not make each edge?

 May 14th, 2013, 06:20 AM #5 Math Team   Joined: Apr 2012 Posts: 1,579 Thanks: 22 Re: Graph Theory - Simple Labelled Graphs Recall that if you multiply x^y*x^z, you add the exponents: x^y*x^z = x^(y+z) So if you DIVIDE x^y by x^z, you SUBTRACT the exponents: x^y/x^z = x^(y-z) You can subtract one fraction from another, whether the fraction occurs as an exponent or otherwise, by setting a common denominator and subtracting one numerator from the other. So a/k-b/k = (a-b)/k Sometimes after subteracting, you can simply the fraction. For instance, (2x+1) - (2y+1) = 2(x-y). So (2x+1)/2-(2y+1)/2 = (2(x-y))/2 = x-y Use all of these to convince yourself that 2^((n)(n+1)/2)/2^((n)(n-1)/2) = 2^n
 May 16th, 2013, 10:09 PM #6 Senior Member   Joined: Jan 2012 Posts: 118 Thanks: 1 Re: Graph Theory - Simple Labelled Graphs Thanks for the help you guys! Ya noo i totally understand the division behind it, and how it simplifies. I was just confused as to how this was categorized as induction. Just because with all of the examples of induction that I have done before it has strictly been that proving one side was equal to the other. I have never had to move the entire right side over to the left, so I was just confused. But I asked my teacher after class this week, and he gave me further clarification. Thanks for all your help

 Tags graph, graphs, labelled, simple, theory

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post lubna_mira Applied Math 0 January 12th, 2014 01:52 PM avnerg Applied Math 0 September 18th, 2013 06:03 AM failure Economics 0 December 23rd, 2011 07:31 AM johnyjj2 Applied Math 0 December 28th, 2010 02:49 PM kec11494 Applied Math 0 December 14th, 2010 06:01 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top