Proving that there exist 2 distinct vertices $u,v$ in $G$ such that $d(u) = d(v)$

Question

I have difficulties understanding the proof given below showing that there exist 2 distinct vertices $u,v$ in $G$ such that $d(u) = d(v)$ where $G$ is a non-trivial graph.

Proof: It's clear that $0 \leq d(x) \leq n-1$ for each $x \in G$. If the above statement is false, then there exist 2 vertices $y$ and $z$ in $G$ such that $d(y) = 0$ and $d(z)=n-1$, which however is impossible.

I'm not sure how they deduce from the falsity of $0 \leq d(x) \leq n-1$ that there exist 2 vertices $y$ and $z$ in $G$ such that $d(y) = 0$ and $d(z)=n-1$.

Answer 1

That isn't the statement they are assuming to be false. Rather, they are assuming that $d(u)\ne d(v)$ for every distinct pair of vertices $u,v$ of $G.$ Since there are $n$ vertices of $G$ and $n$ distinct possible values of $d,$ then in particular, $d$ obtains the values $0$ and $n-1$ at some vertices of $G,$ say $u$ and $v$ respectively. Since $d(u)=0,$ then $u$ isn't adjacent to any of the other vertices of $G,$ and in particular, isn't adjacent to $v.$ Since $d(v)=n-1,$ then $v$ is adjacent to every other vertex of $G,$ and in particular, is adjacent to $u.$ Therein lies the contradiction.

Answer 2

If the above statement is false,

This refers to the problem, not to the thing which was just proved right.

Here are the missing details of the proof:

Proof Assume by contradiction that the problem is wrong. Then each vertex has a different degree.

Now each degree is between $0$ and $n-1$. Therefore there are $n$ possible choices for the degrees. Since there are $n$ vertices, each has a different degree, and there are $n$ choices of degrees, it follows that all $n$ values $0,1,2,3,.., n-1$ are taken.

But then there is a vertex of degree $0$ and one of degree $n-1$. But this is a contradiction (Why?).

Answer 3

You can also use the pigeonhole principle.

Let $G$ have order $n\geq 2 $. Either there exists a vertex of degree $n-1$ or there doesn't. If $G$ has a vertex of degree $n-1$, then there does not exist a vertex of degree $0$ since a vertex of degree $n-1$ implies that $G$ is connected. So the possible degrees for the vertices of $G$ are $1,2,...,n-1$. However, since there are $n-1$ possible degrees and $n$ vertices we know by the pigeonhole principle that at least two vertices have the same degree. If $G$ doesn't have a vertex of degree $n-1$, then there are $n-1$ possible degrees ranging from $0,1,...,n-2$. However, since there are $n-1$ possible degrees and $n$ vertices we know by the pigeonhole principle that at least two vertices have the same degree. Thus there exist $u,v\in V(G)$ such that $d(u)=d(v)$.