A graph with almost all degrees different Is it true that for every $n\geq 3$ one can find an undirected grpah, with no loops or double edges, on $n$ vertices such that there are $n-1$ vertices, all with different degrees? (Clearly there can not be $n$ different degrees by the pigeonhole principle).
Thanks for any help.

If $n$ is odd start with a path of length $2$ otherwise start with a single edge. At each step, add two vertices and connect one of them to all other vertices until you have graph on $n$ vertices and it will have the desired property.
