Show that if $G$ is a connected graph such that the degree of every vertex is one of 3 distinct number and each of these three number is degree of at least one vertex of $G$, then there is a path in $G$ contain three vertices whose degree are distinct.
I tried to let $a,b,c$ ($a,b,c \geq 1$) be the number of vertices of degree $x,y,z$ respectively for $x,y,z$ are distinct. The book told me that I need to consider the path that contain 2 vertices of distinct degree. But I don't understand how this could help me. Can anyone enlighten me please?
Let $X$ be a vertex of degree $x$. Let $P_y$ be a shortest path from $X$ to a vertex of degree $y$ and $P_z$ be a shortest path from $X$ to a vertex of degree $z$. If $P_y$ uses a vertex of degree $z$, or $P_z$ uses a vertex of degree $y$, then we've found the required path.
So we can assume that $P_y=(X,X_1,\ldots,X_k,Y)$ for vertices $X_i$, each of degree $x$, and a vertex $Y$ of degree $y$. Similarly, $P_z=(X,X_1^\prime,\ldots,X_m^\prime,Z)$ for vertices $X_i^\prime$ of degree $x$ and a vertex $Z$ of degree $z$.
Now, what can you do if $P_y\cap P_z=X$? What can you do if $X_i=X_{j}^\prime$ for some $i,j$?