# S.O.S. Mathematics CyberBoard

Your Resource for mathematics help on the web!
 It is currently Sat, 3 Dec 2016 12:40:55 UTC

 All times are UTC [ DST ]

 Page 1 of 1 [ 7 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Simple Graphs RevisitedPosted: Wed, 14 Sep 2005 01:02:48 UTC
 Member of the 'S.O.S. Math' Hall of Fame

Joined: Sat, 23 Oct 2004 05:23:15 UTC
Posts: 458
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.

_________________
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

 Post subject: Posted: Wed, 14 Sep 2005 02:54:42 UTC
 Member of the 'S.O.S. Math' Hall of Fame

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:

where

Top

 Post subject: Posted: Wed, 14 Sep 2005 03:15:41 UTC
 Member of the 'S.O.S. Math' Hall of Fame

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

Top

 Post subject: Posted: Wed, 14 Sep 2005 03:25:20 UTC
 Member of the 'S.O.S. Math' Hall of Fame

Joined: Sat, 23 Oct 2004 05:23:15 UTC
Posts: 458
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

 Post subject: Posted: Wed, 14 Sep 2005 03:28:07 UTC
 Member of the 'S.O.S. Math' Hall of Fame

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:

where

Top

 Post subject: Posted: Wed, 14 Sep 2005 03:31:01 UTC
 Member of the 'S.O.S. Math' Hall of Fame

Joined: Sat, 23 Oct 2004 05:23:15 UTC
Posts: 458
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

 Post subject: Posted: Wed, 14 Sep 2005 03:35:34 UTC
 Member of the 'S.O.S. Math' Hall of Fame

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:

where

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 7 posts ]

 All times are UTC [ DST ]

#### Who is online

Users browsing this forum: No registered users

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

Search for:
 Jump to:  Select a forum ------------------ High School and College Mathematics    Algebra    Geometry and Trigonometry    Calculus    Matrix and Linear Algebra    Differential Equations    Probability and Statistics    Proposed Problems Applications    Physics, Chemistry, Engineering, etc.    Computer Science    Math for Business and Economics Advanced Mathematics    Foundations    Algebra and Number Theory    Analysis and Topology    Applied Mathematics    Other Topics in Advanced Mathematics Other Topics    Administrator Announcements    Comments and Suggestions for S.O.S. Math    Posting Math Formulas with LaTeX    Miscellaneous