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$.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityLet'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$.