» 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!

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.

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.

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.

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?

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.

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).

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........

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.

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?) .

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

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.