My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum


Reply
 
LinkBack Thread Tools Display Modes
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 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?
Jet1045 is offline  
 
May 13th, 2013, 06:56 PM   #2
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 933

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:


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?
CRGreathouse is offline  
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?
Jet1045 is offline  
May 13th, 2013, 08:45 PM   #4
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 933

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?
CRGreathouse is offline  
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
johnr is offline  
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
Jet1045 is offline  
Reply

  My Math Forum > College Math Forum > Applied Math

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 01:52 PM
Graph theory: Linking graph characteristics and minimal cut avnerg Applied Math 0 September 18th, 2013 06:03 AM
Overlaying multiple graphs onto the same graph failure Economics 0 December 23rd, 2011 07:31 AM
graph theory - social networks and reverting the graph johnyjj2 Applied Math 0 December 28th, 2010 02:49 PM
Graph theory - 4 stroke graph kec11494 Applied Math 0 December 14th, 2010 06:01 PM





Copyright © 2017 My Math Forum. All rights reserved.