
Applied Math Applied Math Forum 
 LinkBack  Thread Tools  Display Modes 
May 13th, 2013, 02: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 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: 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, 07:56 PM  #2  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 937 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Graph Theory  Simple Labelled Graphs Quote:
What you want is to look at 2^(n(n+1)/2) / 2^(n(n1)/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, 08: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(n1)/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(n1)/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, 09:45 PM  #4  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 937 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Graph Theory  Simple Labelled Graphs Quote:
Quote:
 
May 14th, 2013, 07: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^(yz) 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/kb/k = (ab)/k Sometimes after subteracting, you can simply the fraction. For instance, (2x+1)  (2y+1) = 2(xy). So (2x+1)/2(2y+1)/2 = (2(xy))/2 = xy Use all of these to convince yourself that 2^((n)(n+1)/2)/2^((n)(n1)/2) = 2^n 
May 16th, 2013, 11: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  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
A graph problem in graph theory!  lubna_mira  Applied Math  0  January 12th, 2014 02:52 PM 
Graph theory: Linking graph characteristics and minimal cut  avnerg  Applied Math  0  September 18th, 2013 07:03 AM 
Overlaying multiple graphs onto the same graph  failure  Economics  0  December 23rd, 2011 08:31 AM 
graph theory  social networks and reverting the graph  johnyjj2  Applied Math  0  December 28th, 2010 03:49 PM 
Graph theory  4 stroke graph  kec11494  Applied Math  0  December 14th, 2010 07:01 PM 