5
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ It's also possible for $N = 5$. Take edges $(1, 2)$, $(1, 3)$, $(1, 4)$, $(1, 5)$, $(2, 3)$, $(2, 5)$. $\endgroup$ – neutron-byte Jan 20 '18 at 22:17
5
$\begingroup$

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:

  1. No vertex has degree $0$.

  2. 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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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