Proving G Has Same Degree Vertices: Graph Theory

[Punkyc7]

Prove that if G is a simple graph with at least two vertices, then G has two or more vertices of the same degree.

Pf/
Assume its true for the base case 2 vertices with no edges or 2 vertices with one edge. Then either the degree is of both is 0 or the degree of both is 1. Therefore both vertices have the same degree.

Now assume true for K vertices. WTS True for K+1 vertices.

Since its true that K vertices have at least one pair of vertices of the same degree it follows immediately that K+1 vertices have at least one pair of vertices of the same degree.I was also thinking about doing this by contradiction and showing that if all the vertices are different degrees then there must be a loop but I was not sure how to say that.

 

[Robert1986]

Prove that if G is a simple graph with at least two vertices, then G has two or more vertices of the same degree.

Pf/
Assume its true for the base case 2 vertices with no edges or 2 vertices with one edge. Then either the degree is of both is 0 or the degree of both is 1. Therefore both vertices have the same degree.

Now assume true for K vertices. WTS True for K+1 vertices.

Since its true that K vertices have at least one pair of vertices of the same degree it follows immediately that K+1 vertices have at least one pair of vertices of the same degree.

Why? Let's say v and w are the two verticies in your K-vertex graph that have the same degree. So you add the (K+1)th vertex, say x. What if there is an edge from x to v but not x to w? Then w and v no longer have the same degree, are they?

I was also thinking about doing this by contradiction and showing that if all the vertices are different degrees then there must be a loop but I was not sure how to say that.

OK, you are on the right track, here. Do you know what the pigeon-hole-principle is? So, if a simple graph G has n-verticies, then what are the options for the degree of a vertex in G?

 

[Punkyc7]

yep I guess you right, it would be easier if there were numbers to see that.

Yeah I know the pigeon hole principle. Wouldn't the degree have to be at most n-1

 

[Robert1986]

Exactly, each vertex can have degree 1, degree 2, ..., or degree n-1. Now, there are n verticies in the graph. Do you see what I see?

 

[Punkyc7]

I don't think so, we have n vertices and at most n-1 edges at any vertex, not sure how that would ensure that two of them are the same, wouldn't we need more edges than vertexes to ensure a loop or multiple edges?

 

[Robert1986]

OK, so you want to show that two verticies have the same degree, not the same edge set. So, any vertex's degree has only n-1 possibilities but there are a total of n verticies. Now, what if no two verticies have the same degree? Do you see a contradiction?

 

[glebovg]

This can be shown using the pigeon hole principle.

 

[Punkyc7]

How can you use the pigeon hole principle? You have n different vertices and you n-1 edges or 0 edges so wouldn't you have n different possibilities for the number of edges?

 

[glebovg]

Assume that the graph has n verticies. Each of those vertices is connected to either 0, 1, 2, …, n - 1 other vertices. If any of the vertices is connected to n - 1 vertices, then it is connected to other vertices, thus ... .

 

[Punkyc7]

the vertex is connected to all of the vertices, but how does that ensure that there are at least two of the same degree? Wouldnt that only tell use something about that one vertex?
Wait I think I got it is it because if there are n vertices and if one of them have n -1 edges then none of them have 0. So if there are n-1 vertices left but we can only choose 1 to n-2 edges with means we have 1 more vertex than the number of edges so there has to be a repeat.Is that right?

 

[glebovg]

It is correct. However, you could simplify it.

 

[Punkyc7]

How would you simplify it. Its two sentences long.

 

[glebovg]

The two most important things to remember are: (1) a proof is a logical argument, and must be clearly structured as such; and (2) your proof should be easily readable to any person with as much mathematical background as you.

 

[Robert1986]

He said "simplify" not "shorten". You probably can't shorten it too much, but you can simplify it.

 

[Punkyc7]

The two most important things to remember are: (1) a proof is a logical argument, and must be clearly structured as such; and (2) your proof should be easily readable to any person with as much mathematical background as you.

I have never been very good at proofs other math I am fine with. Anyways, here it goes
Assume that the graph G is simple and has n vertices and one of the vertices has n-1 edges. Then any of the other vertices can not have 0 edges because our first vertices is connected to all others. So we have n-1 vertices remaining and at most n-2 edges to choose from. By the pigeon hole principle this means that at least 2 vertices share a vertex degree because if we have 1 more vertex then edges to choose available.
QED Is that simpler to understand... sadly it is not shorter.

 

[glebovg]

I think it is much simpler to understand.

Well done.

 

[Punkyc7]

Thank you for you help.

 

[Robert1986]

I have never been very good at proofs other math I am fine with. Anyways, here it goes



Assume that the graph G is simple and has n vertices and one of the vertices has n-1 edges. Then any of the other vertices can not have 0 edges because our first vertices is connected to all others. So we have n-1 vertices remaining and at most n-2 edges to choose from. By the pigeon hole principle this means that at least 2 vertices share a vertex degree because if we have 1 more vertex then edges to choose available.
QED


Is that simpler to understand... sadly it is not shorter.

I don't think this is better. First of all, you start of by saying "assume...one of the verticies has n-1 edges." Then, if I understand, you make the (correct, given the assumption) argument that since each vertex is connected to the first vertex, then all of the other verticies have degree bigger than 0, from which you correctly apply PHP to the other n-1 verticies.


Why do you start off assuming that one vertex has degree n-1? At best, your proof (as stated) only proves the case where one vertex has degree n-1. Unless you are going to do several cases (which is unnecessary, and you didn't do, anyway) you cannot make ANY assumptions about the graph that are not given to you in the statement. You know that G is simple, and that's it. So you know there are no loops, no double edges and no vertex has degree 0. Go from there, don't assume anything else.


The proof should start something like this:

"Let G be a simple graph on n verticies. Each vertex's degree can be as small as 1 or as large as n-1." Then go on from there.

 

[Punkyc7]

where can you go from there if you don't know what you have to start with. You have a bunch of nothing to work with? Would you say wlog assume a vertex has n-1 edges

 

[Robert1986]

No, you do not say anything about a vertex having degree n-1 (or anything for that matter). I sort of see what you mean, but you can skip this step. You go from assuming there is a vertex of degree n-1 to saying exactly what you should say about the other n-1 verticies. In other words, the proof should go something like this:

Let G be a simple graph on n verticies. Each vertex's degree can be as small as 1 or as large as n-1 for a total of n-1 options. Given that there are n verticies and n > n-1, by the PHP at least two verticies have the same degree.

 

[Punkyc7]

but couldn't the vertex degree be as small as 0?

 

[Robert1986]

Yes it could; the proof I gave is not 100% complete. You'll need to add one line to the beginning, along the lines of "Let G be a connected graph on n verticies" (you will have to briefly mention the case where no verticies in G are connected, but this is easy, they all have degree 0.)