# Existence of a simple graph following some conditions

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.

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.