Equivalently, you want a simple graph $G$ on $t_n+1$ vertices such that all degrees are in the set $\{t_1, \dots, t_n\}$ and each degree appears at least once. By induction on $n$. If $n = 1$, take a clique on $t_1+1$ vertices. For $n=2$, take a clique on $t_1$ vertices and an empty graph on $t_2 + 1 - t_1$ vertices, and join them all together. For the inductive step, take an example for the $(n-2)$ tuple $(t_2-t_1, \dots, t_{n-1}-t_1)$. Then add in $t_n - t_{n-1}$ isolated vertices. Finally add in $t_1$ universal vertices.

We'll prove the claim by induction on $n$. Consider the graph $G$ of people, such that there is an edge between two people if and only if they played chess together. For the base case $n=1$, take a clique of $t_1+1$ people. Now assume that the result is true for $n$ and we'll prove that for $n+1$. Start with empty graph $G$ of $t_{n+1}+1$ vertices. Choose a set $S$ of $t_1$ vertices and a set $T$ of $t_{n+1}-t_n$ vertices and disjoint to $S$. The set $G\setminus(S\cup T)$ contains $t_n-t_1+1$ vertices, so we can apply the induction hypothesis for $t_2-t_1,\dots,t_n-t_1$ in $G\setminus(S\cup T)$. Choose the vertices of $S$ to be connected to all other vertices in $G$. The new graph satisfies the required conditions.

A small nitpick in the above solution. math90 wrote: Start with empty graph $G$ of $n+1$ vertices. Chosse a set $S$ of $t_1$ vertices. The set $G\setminus S$ contains $t_{n+1}-t_1+1$ vertices, so we can apply the induction hypothesis for $t_2-t_1,\dots,t_{n+1}-t_1$ in $G\setminus S$. Choose the vertices $S$ to be connected to all other vertices in $G$. The new graph satisfies the required conditions. Small typo: I think you mean that $G$ has $t_{n+1}+1$ vertices. Slightly bigger issue: condition (ii) is violated, as none of the vertices in your construction have degree $t_1$.

Induct on $t_n$. For $t_n = 1$ we have two vertices, just connect them. Now choose an arbitrary vertex $v$ and connect it to all other vertices. Then all of the $t_n$ vertices in $G \setminus v$ must have degrees $t_1 - 1, t_2 - 1, \dots, t_n - 1$ amongst them, with each degree except possibly $t_n - 1$ appearing at least once. If $t_1 \neq 1$ we're done by the induction hypothesis. Otherwise if $t_1 = 1$, choose a set $S$ of $t_n - t_{n - 1} \geq 1$ vertices to be isolated. If $n = 2$ then by making the final vertex an isolated vertex in $G \setminus v$ we are done. Otherwise there are $t_{n - 1}$ vertices in $G \setminus (S \cup v)$ and we want them to have degrees $t_2 - 1, t_3 - 1, \dots, t_{n - 1} - 1$ amongst themselves, with each appearing at least once. This is possible by the induction hypothesis.

A non-inductive construction: Let $m=\left\lceil\frac n2\right\rceil$. Split the people into groups $G_1, G_2, G_3, \ldots, G_{m-1}, G_m, G_{m+1}, \ldots, G_n$ of size $t_1, t_2-t_1, t_3-t_2,\ldots, t_{m-1}-t_{m-2}, t_m-t_{m-1}+1, t_{m+1}-t_m, \ldots, t_n-t_{n-1}$ respectively. For $k<m$, make $G_k$ a clique, and make a complete bipartite graph between $G_k$ and $G_{n+1-i}$ for all $i\ge k$. If $n$ is odd, also make $G_m$ a clique. Then, it is easy to see that every vertex in $G_k$ has degree $t_{n+1-k}$, as desired.

Wow, my solution happens to be identical to that of v_Enhance. Oh well, here it is: We wish to construct a graph $G$ all of whose degrees are in the set $\{t_1<\cdots<t_n\}$ (with each degree hit at least once) and with $t_n+1$ vertices. We proceed by induction on $n$. The join of graphs $A$ and $B$ is the disjoint union of $A$ and $B$, along with all possible edges that connect $A$ and $B$. We claim the problem is true for $n=1$ and $n=2$. For $n=1$, simply consider $K_{t_1+1}$. For $n=2$, the join of $K_{t_1}$ with $t_2-t_1+1$ disjoint vertices works. Now suppose the problem is true for $n-2$. We show it is true for $n$. Let $H$ be the graph for the sequence $t_2-t_1<t_3-t_1<\cdots<t_{n-1}-t_1$. Let $H'$ be $H$ disjoint union with $t_n-t_{n-1}$ vertices. Now, let $G$ be the join of $H'$ with $K_{t_1}$. We see that $G$ works, thus completing the induction, and so the entire problem.

Here is an algorithm that constructs the graph. (Basically inductive/recursive method) Base cases $(n=1, 2)$ are trivial. Let $\{a_1 < a_2 < \cdots < a_m | b\}$ denote the problem with the list $a_i$ and $b$ vertices. Given the list $t_1 < t_2 < \cdots < t_n,$ start with a graph with $t_n+1$ vertices and no edges. first take $t_1$ vertices, and for each of them, form an edge between them and everyone else. Now, each of these $t_1$ vertices have degree $t_n,$ and each of the $t_n + 1 - t_1$ remaining vertices have degree $t_1.$ Set these $t_1$ vertices aside, along with one of the other vertices. There are now $t_n - t_1$ vertices remaining, and each currently has degree $t_1.$ We already have vertices with degrees $t_n$ and $t_1$ so we may remove them from our list. Every other element in the list is decreased by $t_1,$ as all of remaining $t_n - t_1$ vertices already have degree $t_1.$ Our list has been reduced from $\{t_1 < t_2 < \cdots < t_{n-1} < t_n | t_n + 1\}$ to $\{t_2-t_1 < \cdots < t_{n-1} - t_1 | t_n - t_1\}.$ However, $t_n - t_1$ may be greater than $t_{n-1}-t_1 + 1,$ in which case we set aside an additional $t_n - t_{n-1} - 1$ vertices, all of which will have degree $t_1$ in the final configuration. After setting aside all of these vertices, we are left with the remaining $t_{n-1}-t_1+1$ vertices, and the equivalent subproblem is now $\{t_2-t_1 < \cdots < t_{n-1} - t_1 | t_{n-1}-t_1 + 1\},$ and we recurse. (Inductive hypothesis)

We want to construct a graph on $t_n+1$ vertices such at least one vertex has degree $t_i$ for each $i=1,\ldots,n$. We induct on $n$. For $n=2$, we can connect each vertex of a $K_{t_1}$ to each vertex of the graph of $t_2-t_1+1$ isolated vertices. Construct the graph $G$ (made of $t_{n-1}-t_1+1$ vertices) for the sequence $t_2-t_1<t_3-t_1<\cdots < t_{n-1}-t_1$. Connect every vertex of $G$ to each vertex of $K_{t_1}$. Now, there are vertices in $G$ present whose degrees are $t_2,t_3,\ldots,t_{n-1}$. The degrees of the vertices in the $K_{t_1}$ are currently $(t_{n-1}-t_1+1) + (t_1-1) = t_{n-1}$. We need a vertex of degree $t_1$ and a vertex of degree $t_{n}$. So add on $t_{n}-t_{n-1}$ isolated vertices, and connect each to each vertex of the $K_{t_1}$. Now the degrees of the vertices in the $K_{t_1}$ are $t_{n-1}+(t_n-t_{n-1}) = t_n$, and the degrees of the isolated vertices are $t_1$.

We proceed with a double induction on $n$ and $t_n$. Induction on $n$: The base cases, $n=1$ and $n=2$ can be constructed by taking $K_{t_1+1}$ and adding $t_2-t_1+1$ universal vertices to $K_{t_1}$, respectively. For the inductive step, we wish to show that if $(t_1,t_2\ldots t_n)$ works for $n\ge 2$, then $(1,t_1+1,t_2+1\ldots t_n+1)$ also works. Begin with the construction for $(t_1,t_2\ldots t_{n-1})$, add in $t_n-t_{n-1}$ isolated vertices and one universal vertex. Induction on $t_n$: We wish to show that if $(t_1,t_2\ldots t_n)$ works for $n\ge 2$, then $(t_1+1,t_2+1\ldots t_n+1)$ also works. Begin with the construction for $(t_1,t_2\ldots t_n)$, and add in one universal vertex.

Rephrase the problem in terms of graph theory in the natural way. Define a graph to be $(t_1,t_2,\dots,t_n)-\emph{good}$ if it satisfies the conditions in the problem statement for the tuple $(t_1,t_2,\dots,t_n)$. We proceed with strong induction on $n$. For the base case of $n = 1$, a complete graph on $t_1 + 1$ vertices is $(t_1)-\emph{good}$. For the induction step, suppose for some $k\ge 1$ that the problem statement holds for all $n\le k$, and fix a tuple $(t_1,t_2,\dots,t_{k+1})$. First, take $t_1$ vertices and connect each of them to all $t_{k+1}$ other vertices of the graph. If $k = 1$, we are already done. Otherwise, set aside $t_k - t_1 + 1$ of the $t_{k+1} - t_1 + 1$ vertices of degree $1$. By the inductive hypothesis, there exists a $(t_2-t_1, t_3-t_1, \dots, t_k-t_1)-\emph{good}$ graph on these vertices and we're done.

Use induction on $n$. Base cases $n=0$(there's nothing to prove) and $n=1$($K_{t_1}$) are trivial. Now suppose that $n-2$ works. For $n$, select a set $S$ of $t_1$ people and connect everyone in $S$ to everyone else(including others in $S$). Then select another set $T$ of $t_n-t_{n-1}$ people that is disjoint from $S$ and don't connect them to anyone besides the people in $S$. We have reduced the problem to the same problem but with $t_2-t_1$, $t_3-t_1$, $\dots$, $t_{n-1}-t_1$, which is true by our inductive hypothesis. $\blacksquare$

This is fairly straightforward by induction. First, pick one vertex $v$, and assume that the conclusion is true for any $n-1$ variables $t_1, t_2, \dots, t_{n-1}$. Then, label $m = t_n - t_{n-1}$ vertices $v_1, v_2, \dots, v_m$, and let them all have degree $t_n$. Notice that upon connecting all the $v_i$ to each other and also to $v$, all the $v_i$ and $v$ itself will each still require $t_{n-1}$ edges. On the other hand, none of the degrees of the other vertices except for $v$ have changed, thus we can induct down. Furthermore, $v$ will end up having degree $t_n$, thus proving the result.

Okay, my solution is same as #7, but I decided to post it Let $A_{1}, A_{2},\dots, A_{n}$ be disjoint subsets of $V$ such that for every $v \in A_{i}$, we have $\deg v = t_{i}$. For $1 \leq i \leq n$, if $i \neq \left\lceil \frac{n}{2} \right\rceil$ then $|A_{i}| = t_{n-i+1} - t_{n-i}$, if $i = \left\lceil \frac{n}{2} \right\rceil$, then $A_{i} = t_{n-i+1}-t_{n-i}+1$. For $A, B \in V$(not necessary distinct), $connect$ is operation that every $u \in A, v \in B$, if $u$ and $v$ are not adjacent, connect them. For $1 \leq i \leq n$, all $n + 1 - i \leq j \leq n$ connect $A_{i}, A_{j}$. Then our graph satisfies the problem condition, as desired.

Firstly, we prove that $t_1 = 1$, $t_2 = 2, \ldots, t_n = n$ works. We proceed using induction with $n=1,2$ being clearly true. Now add in a vertex and draw an edge tot every vertex. So we end up with $2,3,\ldots,n,n+1,n+1$ degree vertices. Now add in another new vertex and draw an edge and one $\deg = n+1$ vertex. So we go from, \[(1,2,\ldots,n) \rightarrow (1,2,\ldots, n+1,n+2).\]We can do this for $n$ odd and even separately to prove the claim. Also, note that if a sequence $(t_1,t_2,\ldots,t_{n+1})$ works, then $(t_1+1, t_2 + 1, \ldots, t_n + 1)$ also works. To see how, just add in an extra vertex and draw an edge from that vertex to the other vertices in the graph we had for $(t_1,t_2,\ldots, t_n)$. Now, as we have $(1,\ldots, n)$ works, so $(1+(t_1-1), 2+(t_1-1),\ldots, n+(t_1-1))$ also works $\implies (t_1,t_1 + 1,\ldots, t_1 + n-1)$. Now add in another vertex and connect it to all vertices with $\deg = t_1 + 1,\ldots, t_1 + n$ and continue doing this until we reach $(t_1,t_2,t_2+1,\ldots,t_2 + n-2)$. Proceeding similarly, we can reach the case where we have $(t_1,t_2,\cdots,t_n)$ and we are done.

Consider a graph such that it has such that it has subgraphs S1,S2,S3,...S_n-1 such that the degree of the vertices in S_i is equal to i-1. Now set t_n to sum of number of vertices. The t_n+1 person will be connected to each one and therefore our condition will be satisfied

Induct on pair $(n, t_1+t_2+\ldots+t_n)$. Base: $n=0$ - empty graph works, $n=1$ - complete graph works. Assume we proved for $n=k$. Let's prove for $n=k+1$. Let one person play with everybody else, delete this person. Now the number of games are from $t_1-1, \ldots, t_n-1$ and we have $t_n$ players. If $t_1-1 > 0$, we are done(cause the sum of $t_i$ decreased). If $t_1=1$, then let $t_n-t_{n-1}$ people play nobody. Note that we already had a player with $t_n$ games, so we can remove $t_n-1$ from the list. So now we have $t_n-(t_n-t_{n-1})=t_{n-1}$ players left and numbers of games are in the list $t_2-1,t_3-1,\ldots,t_{n-1}-1$, hence we are done.

We will obviously induct on $n$. For the base cases: $\bullet$ For $n=1$ take $K_{t_1+1}$. $\bullet$ For $n=2$ take $t_1$ of them have degree $t_2$ and so other $t_2+1-t_1$ have degree $t_1$. Assume this is true for $n=1$, $\dots$, $N-1$, we will prove this for $n=N$. Have $t_N+1$ vertices. Make sure $t_1$ of them have degree $t_N$, and this means the other $t_N+1-t_1$ have degree $t_1$. And now consider the induced subgraph with the the vertices with degree $t_N$ (and its incident edges) deleted. Now we have $t_N+1-t_1$ vertices left and we need to make sure that the degree set of them is exactly \[0<t_2-t_1<\dots<t_{N-1}-t_1\]Make sure that $t_N-t_{N-1}>0$ vertices have degree $0$ and then apply the induction argument on $n=N-2$.