Question on Simple Graphs - Singapore Forums by SGClub.com
Singapore Forums by SGClub.com
Sitemap Contact Us FAQ Singapore Forums by SGClub.com
Home Photos Member List Register Mark Forums Read  
Go Back Home > Lifestyle > School Life > Math Help » Question on Simple Graphs

Why aren't you a member of SGClub.com yet??

» Join 130,000+ other members in chatting.
» Make lots of new friends here.
» Keep up-to-date with current events.
» Participate in Club outings.
» Download lots of Free Stuff!

Registration just takes 2mins and is absolutely free so join our community today!

I Want to Choose my Own Personal Nickname Now!


Reply
 
LinkBack Thread Tools Display Modes
Old 27th January 2013, 10:38 AM   #1 (permalink)
Cool SGClubber
megaman123 is on a distinguished road

 
Posts: 129
Join Date: Nov 2011
Likes: 7
Liked 11 Times in 10 Posts
Gender:

Question on Simple Graphs

This question is about simple graphs, as in Graph Theory graphs. For those who do not know what are 'graphs' in graph theory, put it simply, they are just dots(vertices) and lines(edges). For a simple graph, the lines of one one dot cannot connect back to the same dot(making a loop) and between any pair of dots there cannot be more than one line connecting them. Read the top part of this page to understand it better: http://mathworld.wolfram.com/SimpleGraph.html

Now here's the question:
Prove that, for any simple graph with at least 2 dots(vertices), there are two dots(vertices) with the same number of lines(edges) connected to it.

Sponsors:

Last edited by megaman123; 27th January 2013 at 11:05 AM.
megaman123 is offline  
Add to megaman123's Reputation Reply With Quote
Old 27th January 2013, 10:45 PM   #2 (permalink)
Addicted SGClubber
Betakuwe has a spectacular aura about

 
Betakuwe's Avatar
 
Posts: 874
Join Date: Sep 2010
Likes: 6
Liked 48 Times in 41 Posts
Gender:

Re: Question on Simple Graphs

Nice problem. Too bad this lonely, dark corner of the forums is pretty inactive for enough people to appreciate the problem. You might want to try the Art of Problem Solving forums.



__________________
Are you ready to get serious?
Betakuwe is offline   Add to Betakuwe's Reputation Reply With Quote
Members who Liked this post by Betakuwe:
Tetrahedron (27th January 2013)
Old 27th January 2013, 11:47 PM   #3 (permalink)
Honesty is a virtue~
Tetrahedron is a jewel in the roughTetrahedron is a jewel in the rough

 
Tetrahedron's Avatar
 
Posts: 1,519
Join Date: Sep 2010
Likes: 16
Liked 156 Times in 111 Posts
Gender:

Re: Question on Simple Graphs

Heh I shall provide an alternate prove.


One thing about a simple graph, is the for a vertice v in a graph G, d(v)<=n-1.
HOWEVER, as no pairs of vertices have the same degree, the minimum degrees of v in G will be a arithmetic progression (1,2,3,4,....,n). Which comes to the contradiction that it is a simple graph.
Hence, it is proven that for any simple graph with at least 2 dots(vertices), there are two dots(vertices) with the same number of lines(edges) connected to it.


Overall Betakuwe's prove is a bit tedious, but you got the job done.

EDIT: For people who are interested in this kind of Mathematics, learning proving methodology will be very helpful. So look it up.

__________________
Currently just a wanderer...

Last edited by Tetrahedron; 27th January 2013 at 11:49 PM.
Tetrahedron is offline   Add to Tetrahedron's Reputation Reply With Quote
Old 27th January 2013, 11:59 PM   #4 (permalink)
Addicted SGClubber
Betakuwe has a spectacular aura about

 
Betakuwe's Avatar
 
Posts: 874
Join Date: Sep 2010
Likes: 6
Liked 48 Times in 41 Posts
Gender:

Re: Question on Simple Graphs

Originally Posted by Tetrahedron View Post
Heh I shall provide an alternate prove.


One thing about a simple graph, is the for a vertice v in a graph G, d(v)<=n-1.
HOWEVER, as no pairs of vertices have the same degree, the minimum degrees of v in G will be a arithmetic progression (1,2,3,4,....,n). Which comes to the contradiction that it is a simple graph.
Hence, it is proven that for any simple graph with at least 2 dots(vertices), there are two dots(vertices) with the same number of lines(edges) connected to it.


Overall Betakuwe's prove is a bit tedious, but you got the job done.

EDIT: For people who are interested in this kind of Mathematics, learning proving methodology will be very helpful. So look it up.
Well, I've never learned anything about Graph theory before. What does d(v) mean?

__________________
Are you ready to get serious?
Betakuwe is offline   Add to Betakuwe's Reputation Reply With Quote
Old 28th January 2013, 12:19 AM   #5 (permalink)
Honesty is a virtue~
Tetrahedron is a jewel in the roughTetrahedron is a jewel in the rough

 
Tetrahedron's Avatar
 
Posts: 1,519
Join Date: Sep 2010
Likes: 16
Liked 156 Times in 111 Posts
Gender:

Re: Question on Simple Graphs

Originally Posted by Betakuwe View Post
Well, I've never learned anything about Graph theory before. What does d(v) mean?
Often, d(v) means the degree of a particular vertex v.

EDIT: Degree means number of lines that is joint to a vertex in case you are not sure.

__________________
Currently just a wanderer...

Last edited by Tetrahedron; 28th January 2013 at 12:25 AM.
Tetrahedron is offline   Add to Tetrahedron's Reputation Reply With Quote
Old 28th January 2013, 12:20 AM   #6 (permalink)
Addicted SGClubber
Betakuwe has a spectacular aura about

 
Betakuwe's Avatar
 
Posts: 874
Join Date: Sep 2010
Likes: 6
Liked 48 Times in 41 Posts
Gender:

Re: Question on Simple Graphs

Originally Posted by Tetrahedron View Post
Often, d(v) means the degree of a particular vertex v.
Idk what that means.

__________________
Are you ready to get serious?
Betakuwe is offline   Add to Betakuwe's Reputation Reply With Quote
Old 28th January 2013, 12:26 AM   #7 (permalink)
Honesty is a virtue~
Tetrahedron is a jewel in the roughTetrahedron is a jewel in the rough

 
Tetrahedron's Avatar
 
Posts: 1,519
Join Date: Sep 2010
Likes: 16
Liked 156 Times in 111 Posts
Gender:

Re: Question on Simple Graphs

Originally Posted by Betakuwe View Post
Idk what that means.
Look above. Explained it too.

__________________
Currently just a wanderer...
Tetrahedron is offline   Add to Tetrahedron's Reputation Reply With Quote
Old 28th January 2013, 12:33 AM   #8 (permalink)
Addicted SGClubber
Betakuwe has a spectacular aura about

 
Betakuwe's Avatar
 
Posts: 874
Join Date: Sep 2010
Likes: 6
Liked 48 Times in 41 Posts
Gender:

Re: Question on Simple Graphs

Originally Posted by Tetrahedron View Post
Look above. Explained it too.
How does one know that a graph where the degrees are in an arithmetic progression is not a simple graph?

__________________
Are you ready to get serious?
Betakuwe is offline   Add to Betakuwe's Reputation Reply With Quote
Old 28th January 2013, 12:34 AM   #9 (permalink)
Honesty is a virtue~
Tetrahedron is a jewel in the roughTetrahedron is a jewel in the rough

 
Tetrahedron's Avatar
 
Posts: 1,519
Join Date: Sep 2010
Likes: 16
Liked 156 Times in 111 Posts
Gender:

Re: Question on Simple Graphs

For Betakuwe to refer to. Includes all the logic behind my answers and some stuff about mathematical proving.


One thing about a simple graph, is the for a vertice v in a graph G, d(v)<=n-1.

This meant that for any vertex in a simple graph, the maximum number of edges connected to the vertex is n-1, where n is the number of vertex.

HOWEVER, as no pairs of vertices have the same degree, the minimum degrees of v in G will be a arithmetic progression (1,2,3,4,....,n). Which comes to the contradiction that it is a simple graph.

It is important to note that for almost all the things in graph theory, it must be a positive integer. Hence, suppose we try to keep the degree to the minimum, when degree 1 is taken, the next lowest number will be 2. Hence for no 2 vertices to have the same degree, it will follow up to n in an arithmetic progression. HOWEVER, in actual mathematical prove, it would be wise to put the inequality sign to further justify the logic of the prove.

To answer your question above, look at the last vertex of the arithmetic sequence. To further complete my prove, I would need to say that there will be at least 1 vertex which have a degree n or higher, which is a contradiction. However due to my laziness I did not include this statement in.

In addition, contradiction is one of the proving methods possible to prove a statement. Common ways of prove is direct (what Betakuwe just done), contrapositive (taking the reverse logic of the statement), induction (which will be taught in H2 Math in JC), and contradiction (going both ways, and prove that it doesn't make sense.) As you can tell, I am a dude which prefer contradiction, but it is up to you really.


Hence, it is proven that for any simple graph with at least 2 dots(vertices), there are two dots(vertices) with the same number of lines(edges) connected to it.

This statement is just to make the answer more fluent.


__________________
Currently just a wanderer...

Last edited by Tetrahedron; 28th January 2013 at 12:36 AM.
Tetrahedron is offline   Add to Tetrahedron's Reputation Reply With Quote
Old 28th January 2013, 12:42 AM   #10 (permalink)
Addicted SGClubber
Betakuwe has a spectacular aura about

 
Betakuwe's Avatar
 
Posts: 874
Join Date: Sep 2010
Likes: 6
Liked 48 Times in 41 Posts
Gender:

Re: Question on Simple Graphs

Originally Posted by Tetrahedron View Post
For Betakuwe to refer to. Includes all the logic behind my answers and some stuff about mathematical proving.


One thing about a simple graph, is the for a vertice v in a graph G, d(v)<=n-1.

This meant that for any vertex in a simple graph, the maximum number of edges connected to the vertex is n-1, where n is the number of vertex.

HOWEVER, as no pairs of vertices have the same degree, the minimum degrees of v in G will be a arithmetic progression (1,2,3,4,....,n). Which comes to the contradiction that it is a simple graph.

It is important to note that for almost all the things in graph theory, it must be a positive integer. Hence, suppose we try to keep the degree to the minimum, when degree 1 is taken, the next lowest number will be 2. Hence for no 2 vertices to have the same degree, it will follow up to n in an arithmetic progression. HOWEVER, in actual mathematical prove, it would be wise to put the inequality sign to further justify the logic of the prove.

To answer your question above, look at the last vertex of the arithmetic sequence. To further complete my prove, I would need to say that there will be at least 1 vertex which have a degree n or higher, which is a contradiction. However due to my laziness I did not include this statement in.

In addition, contradiction is one of the proving methods possible to prove a statement. Common ways of prove is direct (what Betakuwe just done), contrapositive (taking the reverse logic of the statement), induction (which will be taught in H2 Math in JC), and contradiction (going both ways, and prove that it doesn't make sense.) As you can tell, I am a dude which prefer contradiction, but it is up to you really.


Hence, it is proven that for any simple graph with at least 2 dots(vertices), there are two dots(vertices) with the same number of lines(edges) connected to it.

This statement is just to make the answer more fluent.

Lol okay, I feel silly now for not noticing such a simple thing. Protip: Put quote tags inside spoiler tags to make them easier to read(or maybe it's just my issue with the dotted lines).

__________________
Are you ready to get serious?
Betakuwe is offline   Add to Betakuwe's Reputation Reply With Quote
Old 29th January 2013, 08:11 AM   #11 (permalink)
Experienced SGClubber
namelessname is a jewel in the roughnamelessname is a jewel in the rough

 
Posts: 6,148
Join Date: Jun 2007
Likes: 167
Liked 28 Times in 25 Posts
Gender:

Re: Question on Simple Graphs

Haha well done by all, you all are so pro.....

I am thinking of the pigeon hole method.

possible d(v) = n - 1. So there is n - 1 pigeon hole.
But since there is n vertices = n balls to be put into n - 1 pigeon hole, there is definitely one pigeon hole with at least 2 balls........

namelessname is offline   Add to namelessname's Reputation Reply With Quote
Old 29th January 2013, 10:08 AM   #12 (permalink)
Honesty is a virtue~
Tetrahedron is a jewel in the roughTetrahedron is a jewel in the rough

 
Tetrahedron's Avatar
 
Posts: 1,519
Join Date: Sep 2010
Likes: 16
Liked 156 Times in 111 Posts
Gender:

Re: Question on Simple Graphs

Originally Posted by namelessname View Post
Haha well done by all, you all are so pro.....

I am thinking of the pigeon hole method.

possible d(v) = n - 1. So there is n - 1 pigeon hole.
But since there is n vertices = n balls to be put into n - 1 pigeon hole, there is definitely one pigeon hole with at least 2 balls........
Yes that is almost the same method as mine. Proving that the graph will not be simple.

__________________
Currently just a wanderer...
Tetrahedron is offline   Add to Tetrahedron's Reputation Reply With Quote
Old 29th January 2013, 10:14 AM   #13 (permalink)
Experienced SGClubber
namelessname is a jewel in the roughnamelessname is a jewel in the rough

 
Posts: 6,148
Join Date: Jun 2007
Likes: 167
Liked 28 Times in 25 Posts
Gender:

Re: Question on Simple Graphs

Originally Posted by Tetrahedron View Post
Yes that is almost the same method as mine. Proving that the graph will not be simple.
yah, actually quite glad to see some math-inclined sgcian around. lol. didnt expect much from a pretty dead forum.

namelessname is offline   Add to namelessname's Reputation Reply With Quote
Old 29th January 2013, 11:47 AM   #14 (permalink)
Honesty is a virtue~
Tetrahedron is a jewel in the roughTetrahedron is a jewel in the rough

 
Tetrahedron's Avatar
 
Posts: 1,519
Join Date: Sep 2010
Likes: 16
Liked 156 Times in 111 Posts
Gender:

Re: Question on Simple Graphs

Originally Posted by namelessname View Post
yah, actually quite glad to see some math-inclined sgcian around. lol. didnt expect much from a pretty dead forum.
It will be pretty much flooded when the exams are near.

__________________
Currently just a wanderer...
Tetrahedron is offline   Add to Tetrahedron's Reputation Reply With Quote
Old 30th January 2013, 12:34 PM   #15 (permalink)
Cool SGClubber
megaman123 is on a distinguished road

 
Posts: 129
Join Date: Nov 2011
Likes: 7
Liked 11 Times in 10 Posts
Gender:

Re: Question on Simple Graphs

Originally Posted by Tetrahedron View Post
Heh I shall provide an alternate prove.


One thing about a simple graph, is the for a vertice v in a graph G, d(v)<=n-1.
HOWEVER, as no pairs of vertices have the same degree, the minimum degrees of v in G will be a arithmetic progression (1,2,3,4,....,n). Which comes to the contradiction that it is a simple graph.
Hence, it is proven that for any simple graph with at least 2 dots(vertices), there are two dots(vertices) with the same number of lines(edges) connected to it.


Overall Betakuwe's prove is a bit tedious, but you got the job done.

EDIT: For people who are interested in this kind of Mathematics, learning proving methodology will be very helpful. So look it up.
Neat, you got the idea... lol you forgot that d(v)=0 is also possible... so.. (0,1,2,...,n-1) for an n vertex graph. Hence no contradiction with d(v)<=n-1. But even so... you should realise for (0,1,2,...,n-1), this kind of graph cannot exist (why?) .

megaman123 is offline   Add to megaman123's Reputation Reply With Quote
Old 30th January 2013, 12:37 PM   #16 (permalink)
Cool SGClubber
megaman123 is on a distinguished road

 
Posts: 129
Join Date: Nov 2011
Likes: 7
Liked 11 Times in 10 Posts
Gender:

Re: Question on Simple Graphs

Originally Posted by Betakuwe View Post
Nice problem. Too bad this lonely, dark corner of the forums is pretty inactive for enough people to appreciate the problem. You might want to try the Art of Problem Solving forums.

Wow nice attempt on the question. Planning to take maths when you go uni? LOL

megaman123 is offline   Add to megaman123's Reputation Reply With Quote
Old 30th January 2013, 02:37 PM   #17 (permalink)
Honesty is a virtue~
Tetrahedron is a jewel in the roughTetrahedron is a jewel in the rough

 
Tetrahedron's Avatar
 
Posts: 1,519
Join Date: Sep 2010
Likes: 16
Liked 156 Times in 111 Posts
Gender:

Re: Question on Simple Graphs

Originally Posted by megaman123 View Post
Neat, you got the idea... lol you forgot that d(v)=0 is also possible... so.. (0,1,2,...,n-1) for an n vertex graph. Hence no contradiction with d(v)<=n-1. But even so... you should realise for (0,1,2,...,n-1), this kind of graph cannot exist (why?) .
Aiya I am lazy on this one. Knew that that is possible, just lazy to write.

When there is 1 vertex with d(v)=0, it is disconnected. So now the maximum degree of the graph will be n-2, and not n-1, which is again a contradiction.

__________________
Currently just a wanderer...
Tetrahedron is offline   Add to Tetrahedron's Reputation Reply With Quote
Reply

Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Just a simple question. hello1214 Love & Relationships 15 2nd November 2012 03:57 PM
Erm a simple question zeroracer Math Help 3 30th October 2011 10:02 PM
A simple question. By2 Health & Fitness 0 20th July 2011 11:48 PM
Just a simple question... christmas_ SGClub Cafe 18 15th November 2010 04:45 PM
Help: 3 SIMPLE QUESTION ABOUT ITE U F O School Life 3 28th September 2009 10:04 PM

» Sponsors
Watch Free Movies Online
Celebrity Gossip
Food Delivery

» Facebook Fans
» What's Going On?
Title, Username, & Date
Repost comment.
Stupid court of appeal gives red light running driver who hit pedestrian 15% discount
Mum's Kitchen Catering and Cherish Delights get licences suspended after nearly 40 people...
[PMD-pedestrian rules] Singapore Court judges are high handed and biased or court rep
Post anything random on this thread.
Ritter Sport chocolate recalled due to undeclared allergen
Aoki Hagane no Arpeggio: Ars Nova
I really hate my mother!!!
Transcend RDF9K2 All-in-One Card Reader
Transcend ESD250C, a portable SSD that’s super classy
How PAP exploited racial differences to impose FASCIST rule over Singapore.
Up to S$7250 of government $ misused for buying each vote in Singapore?
Funky Fields organic vegan spreadable recalled due to 'undisclosed allergen'
100 hawksbill turtles released into the sea after rare hatching on Sentosa
Inspirational Songs
MOH, SFA investigating after 18 typhoid fever cases in 3 weeks
By militarily invading Hong Kong, Xi Jingping is setting in motion, the wheels of nuc
Deng XiaoPing original vision for HKG- China reunification was for the two to unite a
HSA warns against three products
Warning : Blacklist buyer/adopter Alert
Featured Photos
by marisoljames322
· · ·
Member Galleries
20359 photos
13619 comments
by marisoljames322
· · ·
Member Galleries
20359 photos
13619 comments
by pdsubbu
· · ·
Member Galleries
20359 photos
13619 comments
by Vikas Dhar
· · ·
Photography
35 photos
36 comments
by aaudreygan
· · ·
Guy Photos
1581 photos
946 comments
by aaudreygan
· · ·
Girl Photos
4351 photos
28607 comments
by a8paris
· · ·
Guy Photos
1581 photos
946 comments
by a8paris
· · ·
Guy Photos
1581 photos
946 comments
by aaricia
· · ·
Girl Photos
4351 photos
28607 comments
by aaricia
· · ·
Girl Photos
4351 photos
28607 comments

 

All times are GMT +8. The time now is 12:38 AM.


Powered by vBulletin
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
Copyright© 2004-2013 SGClub.com. All rights reserved.