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.

-
Why the restriction on $n \ge 3$? It seems to be true for $n = 1$ and $2$ also. :) – Rahul May 30 '12 at 19:57
But then it is trivial :) – Dennis Gulko May 30 '12 at 20:01

2 Answers

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.

-
thanks, a very nice proof! – Dennis Gulko May 30 '12 at 20:04

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.

-