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