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

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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.