Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 10 down vote accepted

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.

share|cite|improve this answer
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.