# A simple graph must have at least one pair of vertices whose degrees are equal.

I came across this proof while studying graph theory and although it instinctively makes sense, I have a problem with a part of it.

Proposition: A non-trivial simple graph $$G$$ must have at least one pair of vertices whose degrees are equal.

Proof: Let $$G$$ be a graph with $$n$$ vertices. Because $$G$$ is a simple graph, then by definition it doesn't contain multi-edges or loops. Therefore, there appears to be $$n$$ possible degree values for any vertex, namely $$0, ..., n-1$$. However, there cannot be both a vertex of degree 0 and a vertex of degree $$n - 1$$, since the presence of a vertex of degree 0 implies that each of the remaining $$n - 1$$ vertices is adjacent to at most $$n-2$$ other vertices. Hence, the $$n$$ vertices of $$G$$ can realize at most $$n − 1$$ possible values for their degrees [This is the part where I have troubles]. Thus, the pigeonhole principle implies that at least two of the $$n$$ vertices have equal degree.

Isn't this proof based on assumption that there exists a vertex with degree $$0$$. What happens if that is not case? Does the proof still hold? And why can the $$n$$ vertices of the graph realize at most $$n-1$$ possible values? I don't understand that step.

No, there is no assumption that the graph has a vertex of degree $$0$$: there is simply the observation that it is impossible for a graph on $$n$$ vertices to have both a vertex of degree $$0$$ and a vertex of degree $$n-1$$. If $$G$$ has a vertex $$v$$ of degree $$n-1$$, that vertex is adjacent to all of the other $$n-1$$ vertices of $$G$$, and therefore all of those vertices have degree at least $$1$$, because they all have an edge to $$v$$. Thus, $$G$$ cannot have both a vertex of degree $$n-1$$ and a vertex of degree $$0$$.

This means that if $$G$$ has a vertex of degree $$n-1$$, the only other possible degrees of its vertices are $$1,2,\ldots,n-2$$: degree $$0$$ is not possible. Thus, it can have at most the $$n-1$$ different degrees $$1,\ldots,n-1$$. And if it has a vertex of degree $$0$$, the only other possible degrees of its vertices are $$1,2,\ldots,n-2$$: degree $$n-1$$ is not possible. In this case it can have at most the $$n-1$$ degrees $$0,\ldots,n-2$$.

And of course if $$G$$ has neither a vertex of degree $$0$$ nor a vertex of degree $$n-1$$, the only possible degrees of its vertices are $$1,\ldots,n-2$$, so that it can have at most these $$n-2$$ degrees.

In every case, then, $$G$$ can have at most $$n-1$$ different degrees for its $$n$$ vertices, and the pigeonhole principle immediately tells us that two of the vertices must have the same degree.

• Wow, very simple when you put it that way. Thanks for the clarification. – Marwan Jan 16 at 9:50
• @Marwan: You’re welcome. – Brian M. Scott Jan 16 at 18:14

There are $$n$$ vertices and there are $$n$$ possible degrees: $$0,1,\ldots, n-1$$. If no two vertices have same degree, then each possible degree must be attained. In particular, there must be one vertice $$v$$ of degree $$0$$ and one vertex $$w$$ of degree $$n-1$$. If $$n>1$$, this is a contradiction

Consider two cases:

1. There is a vertex of degree $$0$$. Then the other degrees are in $$0,1,\ldots, n-2$$. So the degrees are $$n$$ elements of $${0,1,\ldots, n-2}$$ which has size $$n-1$$. Hence two of the degrees coincide.

2. There is no vertex of degree $$0$$. Then the other degrees are in $$1,\ldots, n-2, n-1$$. So the degrees are $$n$$ elements of $${1,\ldots, n-1}$$ which has size $$n-1$$. Hence two of the degrees coincide.