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$.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ It's also possible for $N = 5$. Take edges $(1, 2)$, $(1, 3)$, $(1, 4)$, $(1, 5)$, $(2, 3)$, $(2, 5)$. $\endgroup$– neutron-byteJan 20, 2018 at 22:17
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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$.
