If G is a simple graph with at least two vertices, prove that G must contain two or more vertices of the same degree.

graph theoryproof-writing

I will use the pigeon-hole principle.

For a simple graph of n vertices the maximum degree a vertex can have is (n-1).
Let there be (n-1) boxes corresponding to degrees of 1 to (n-1). We are going to put the vertices into the box with the degree it has. As there are n vertices, by the pigeon hole principle, at least two of the vertices must be in the same box so that all vertices can fit into the boxes.
Here we assume that the each vertex at least have a degree of 1. If some k number of vertices have degrees of zero, the argument is still valid as the boxes can simply be reduced to n-k-1 and if k>=2 then at least two other vertices also have the same degree.

Edit
As mentioned by 5xum below, the problem only occurs when k=1, so the only reduction needed is to n-2 boxes.

Best Answer

We notice that the vertices that occurs the same number of times in the sequence results in having the same degree. (Do I have to prove this?)

A short sentence about why this is true in general would be nice, yes.

Something like "since each appearance of a vertex in the sequence corresponds in one removal of an edge starting at that vertex, we see that the degree of the vertex is $(n-1)-k$, where $k$ is the number of appearances of the vertex in the sequence".

Anyway, your proof has a much bigger problem later on. In particular, you claim the following is true:

If some vertex occurs some j times less than (n-1) then by the nature of edges, at least one other edge must also occur j times.

yet you provide no proof. How do you know this is true? The way I see it, this claim is just an elaborate restatement of the original theorem that you are yet to prove, so you cannot just assert it is true.

Even more in particular, the problem is also here:

From this let's remove from the sequence one of the edges(so now it will occur n-2 times), in other words, we are removing one less edge. Then, one other edge also occurs n-2 times. So at least 2 vertices are of the same degree as the others essentially occur the same time.

well... sure. But all this shows is that if you remove one edge from a full graph, you get two vertices with degree $n-2$.

But then you say:

We could do this repeatedly

How do you know this? You demonstrated the claim on a very specific type of graph (i.e., a full graph), and then claim that the same is true on all graphs. You cannot do that.

Edit:

You now also demonstrated the claim on another specific type of graphs (those that can be constructed from a full graph by removing one edge), but you still haven't shown it on all graphs.

Edit #2

Your new approach is a good idea, but it needs some work. The way you did it is ok, but can be made a little clearer. When analyzing the case when $k$ vertices have degree $0$, you can first say that the only issue appears when $k=1$ (otherwise, two vertices have degree $0$ and we are done), and then explain that if one vertex has degree $0$, then the maximum degree of the others is $n-2$.

Related Question