Suppose, $a_1 < a_2 < \cdots < a_k$ are distinct positive integers. I am trying to prove that there exists a simple graph with $(a_k + 1)$ many vertices, whose set of distinct vertex degrees is $a_1, a_2, \cdots , a_k$.

I was trying to use induction on k. I solved using induction when $a_i = i , \forall i$. But could not do the general case.

Any help will be appreciated. Thanks in advance.


2 Answers 2


A trick with complements helps. If a graph has $a_k+1$ vertices and the set of distinct degrees is $\{a_1, a_2, \dots, a_k\}$, then its complement is a graph with $a_k + 1$ vertices where the set of distinct degrees is $\{a_k-a_1, a_k - a_2, \dots, a_k - a_{k-1}, 0\}$.

The zero degrees are easy to tack on at the end, so now we have reduced to a smaller problem: find a graph with fewer than $a_k+1$ vertices where the set of distinct degrees is $\{a_k - a_1, a_k - a_2, \dots, a_k - a_{k-1}\}$. This can be done by induction.


Put $a_1$ vertices of degree $a_k$ and $a_k-a_{k-1}$ vertices of degree $a_1$. The number of vertices remaining is $a_k + 1 - a_1 - (a_k-a_{k-1}) = a_{k-1}-a_1+1$.
We are reduced to the sequence : $a_2 - a_1, a_3-a_1..., a_{k-1}-a_1$, so induction applies.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .