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.

You can induct. Let $G_n$ be such a graph on $n$ vertices; then your pigeonhole argument shows that $G_n$ has either a vertex of degree $n-1$ or a vertex of degree $0$, but not both. Also, its complement $\tilde{G_n}$ is another such graph, which has a vertex of degree $0$ iff $G_n$ does not. So we can suppose without loss of generality that $G_n$ has no vertex of degree $0$. But then the union of $G_n$ with an isolated vertex is such a graph on $n+1$ vertices.
