Graph where only two vertices have the same degree

Let's say that $N$ is the number of vertices. We want to create a graph where only two vertices have the same degree. For what kind of $N$ is this possible?

I tried it and I've been able only to come up with such where $N$ is $3$ and $4$.

It is possible for every $N\ge 2$. We can prove it by mathematical induction.

For $N=2$, it is trivial.

Suppose there is such a graph for $N=n$, there are following two cases:

-
No vertex has degree $0$.

-
There is a vertex with degree $0$.

In case 1, we just add an isolated vertex. Now the graph has $n+1$ nodes and only two vertexes in the previous graph have the same degree.

In case 2, no vertex has degree $n-1$. We add a vertex with edges to every vertex in previous graph. The new node has degree $n$. The degree of each vertex in previous graph is added by $1$, thus no one in the new graph has degree $n$. Now the graph has $n+1$ nodes and only two vertexes in the previous graph have the same degree.

So such graph is possible for $N=n+1$.

As a conclusion, it is possible for every $N\ge 2$.

If you only care about connected graph (i.e. no vertex has degree $0$), the result is the same while the proof should be revised somewhat: the new graph for $N=n+1$ is constructed via first constructing an intermediate graph for $N=n$ from the graph for $N=n-1$ (this intermediate graph has a vertex with degree $0$), then constructing the graph for $N=n+1$.

StackExchange Computer Science Q#87039, answer score: 5