Graph Theory Pigeonhole Principle Question [duplicate]
Solution 1:
Let $v$ be the vertex of the greatest degree and let $\operatorname{deg}(v)=k>0$. Let $N(v)$ be neighbors of vertex $v$. Then the degrees of all vertices from $N(v)$ are pairwise distinct, and if there are no vertices of degree 1 among them, then there must be a vertex of degree $k+1$ or more. This contradicts the choice of vertex $v$.