S.O.S. Mathematics CyberBoard

Your Resource for mathematics help on the web!
It is currently Sat, 25 Oct 2014 17:45:14 UTC

All times are UTC [ DST ]




Post new topic Reply to topic  [ 7 posts ] 
Author Message
 Post subject: Simple Graphs Revisited
PostPosted: Wed, 14 Sep 2005 01:02:48 UTC 
Offline
Member of the 'S.O.S. Math' Hall of Fame
User avatar

Joined: Sat, 23 Oct 2004 05:23:15 UTC
Posts: 443
Location: New Jersey, USA
Hi all! I had posted a problem under "Simple Graphs" earlier but didn't show how I approached it.

Here's the problem again:

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!

Would it be enough to give this as a proof for the first part?

Proof:

n is the number of vertices.

For n = 1 we have 1 labelled simple graph

For n = 2 we have 2 labelled simple graphs

For n = 3 we have 8 labelled simple graphs

For n = 4 we have 64 labelled simple graphs

. . . and so on. . .

we see a pattern

1, 2, 8, 64, . . .

which is

2^0, 2^1, 2^3, 2^4, . . .

the nth term of this sequence is 2^(n(n-1)/2) and therefore there must be this many simple labelled graphs on n vertices.

Please comment on this. Thanks!

_________________
Mathematics is one of the essential emanations of the human spirit, a thing to be valued in and for itself, like art or poetry. -- Oswald Veblen, 1924.


Top
 Profile  
 
 Post subject:
PostPosted: Wed, 14 Sep 2005 02:54:42 UTC 
Offline
Member of the 'S.O.S. Math' Hall of Fame
User avatar

Joined: Sun, 4 May 2003 16:04:19 UTC
Posts: 2906
plz post under the original topic in the future

_________________
Has anyone noticed that the below is WRONG? Otherwise this statement would be true:
-1\cong1\pmod{13}
i\cong5 \pmod{13} where
i^2=-1


Top
 Profile  
 
 Post subject:
PostPosted: Wed, 14 Sep 2005 03:15:41 UTC 
Offline
Member of the 'S.O.S. Math' Hall of Fame
User avatar

Joined: Wed, 1 Oct 2003 04:45:43 UTC
Posts: 9834
What you wrote does not qualify as a proof. Try induction.


Top
 Profile  
 
 Post subject:
PostPosted: Wed, 14 Sep 2005 03:25:20 UTC 
Offline
Member of the 'S.O.S. Math' Hall of Fame
User avatar

Joined: Sat, 23 Oct 2004 05:23:15 UTC
Posts: 443
Location: New Jersey, USA
Matthew wrote:
What you wrote does not qualify as a proof. Try induction.


OK. So let me see where I can get with induction on n, the number of vertices of the simple graphs.


Claim:

2^(n(n-1)/2) is the total number of labelled simple graphs on n vertices.

Proof:

Induction on n.

Basis Step:

For n = 1, the claim is true and can be verified by drawing.

Assume it is also true for n. (Inductive Hypothesis)

Then, we need to show that it is also true for n + 1.

That is,

2^((n+1)(n+1-1)/2) = 2^(n(n+1)/2)

How do I show this???

_________________
Mathematics is one of the essential emanations of the human spirit, a thing to be valued in and for itself, like art or poetry. -- Oswald Veblen, 1924.


Top
 Profile  
 
 Post subject:
PostPosted: Wed, 14 Sep 2005 03:28:07 UTC 
Offline
Member of the 'S.O.S. Math' Hall of Fame
User avatar

Joined: Sun, 4 May 2003 16:04:19 UTC
Posts: 2906
see the other post. as i said, its really annoying and impolite (bah... ) when people opens double post on the same question. then it waste time and effort for everyone having to check both or even posting replies twice.

and did you see my other post? it's rude to not reply to it and instead post it here again, hoping someone would solve the problem for you. as i said, dont be lazy. its not hard. i've given you enough hints on that, you should have no problems completing that problem now.

_________________
Has anyone noticed that the below is WRONG? Otherwise this statement would be true:
-1\cong1\pmod{13}
i\cong5 \pmod{13} where
i^2=-1


Top
 Profile  
 
 Post subject:
PostPosted: Wed, 14 Sep 2005 03:31:01 UTC 
Offline
Member of the 'S.O.S. Math' Hall of Fame
User avatar

Joined: Sat, 23 Oct 2004 05:23:15 UTC
Posts: 443
Location: New Jersey, USA
bugzpodder wrote:
see the other post. as i said, its really annoying and impolite (bah... ) when people opens double post on the same question. then it waste time and effort for everyone having to check both or even posting replies twice.


Is 2^((n(n-1))/2) the total number of NON-ISOMORPHIC simple graphs on n vertices?

_________________
Mathematics is one of the essential emanations of the human spirit, a thing to be valued in and for itself, like art or poetry. -- Oswald Veblen, 1924.


Top
 Profile  
 
 Post subject:
PostPosted: Wed, 14 Sep 2005 03:35:34 UTC 
Offline
Member of the 'S.O.S. Math' Hall of Fame
User avatar

Joined: Sun, 4 May 2003 16:04:19 UTC
Posts: 2906
1) please post in the OTHER topic
2) this is the number of simple graphs. if the word "non-isophmorphic" applies any kind of restriction that removes even one simple graph, then no.

_________________
Has anyone noticed that the below is WRONG? Otherwise this statement would be true:
-1\cong1\pmod{13}
i\cong5 \pmod{13} where
i^2=-1


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 7 posts ] 

All times are UTC [ DST ]


Who is online

Users browsing this forum: No registered users


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Search for:
Jump to:  
Contact Us | S.O.S. Mathematics Homepage
Privacy Statement | Search the "old" CyberBoard

users online during the last hour
Powered by phpBB © 2001, 2005-2011 phpBB Group.
Copyright © 1999-2013 MathMedics, LLC. All rights reserved.
Math Medics, LLC. - P.O. Box 12395 - El Paso TX 79913 - USA