For every $n\in \Bbb{N}$ there exists a graph with $2n$ vertices with the degrees: $1, 1, 2, 2, 3, 3 \dots n, n$ Prove/disprove: 

For every $n\in \Bbb{N}$ there exists a simple graph (without loops
  and multiple edges) with $2n$ vertices with the degrees: $1, 1, 2, 2,
> 3, 3 \dots n, n$

Is this statement true? 
Please help me approach this.
Note: Degree is defined as the number of neighbors.
 A: Let $A_n$ be the $n \times n$ matrix consiting of zero's below the leading diagonal and ones on and above the leading diagonal.
\begin{eqnarray*}
A_n=
\begin{bmatrix}
1  &1 & \cdots  & 1 \\
0  &1 & \cdots  & 1 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & 1 \\
\end{bmatrix} 
\end{eqnarray*}
The bipartitite graph whose adjacency matrix has the following block structure will have the desired property
\begin{eqnarray*}
B_{2n}=
\begin{bmatrix}
0_n  & A_n  \\ A_n^{T}  &0_n \\
\end{bmatrix} .
\end{eqnarray*}
Edit: So vertex $1$ is joined to $n+1,\cdots,2n$. 
Vertex $2$ is joined to $n+2,\cdots,2n$. 
Vertex $3$ is joined to $n+3,\cdots,2n$. and so on until $n$ is only joined to $2n$.
A: This argument is true. And we can prove it using induction on $n$.
For $n = 1$, obviously the graph exists. Now suppose, inductively, that argument holds for all $n$. Then for $n+1$, let's try to add two new vertices to the graph with $2n$ vertices, whose existence is assumed by inductive argument.
Notice that we can connect one of the new vertices to the vertex with degree $n$ to get a vertex with degree $n+1$. When we do that, our new vertex will have the degree $1$. Then in order to have a vertex with degree $n$, we can connect new vertex to a vertex with degree $n-1$ (Since we lost the vertex with degree $n$ when we connect it to the new vertex). Now our new vertex has degree $2$. Notice that when we are increasing the degree of the new vertex, we are losing a vertex that satisfies the condition (When new vertex has degree $k$, we lose the vertex with degree $n-k+1$). Now suppose we are using the same process symmetrically, I mean, for the second vertex, we are doing the same since we have pairs of vertices with same degree. Now, we should notice that;


*

*When $n$ is even, say $2k$, at $k$'s step, we will lose the vertex with degree $k+1$ and our new vertices will have degree $k$. At this point, we can simply connect them together to renew the vertices with degree $k+1$. Since we don't go further in this process, vertices with degrees $1,2,...,k$ are already conserved. So we are done.

*When $n$ is odd, say $2k+1$, at $k+1$'s step, we will lose the vertices with degree $k+1$ however new vertices will have degree $k+1$ so they are conserved. By similar reason to above, we are done.
Therefore by induction, argument holds for all $n$.
Here is an example for $n = 3$, $n = 4$ and $n = 5$:

A: Here is a simple argument by induction:
Base: $n=1$: trivial: put an edge between the two vertices.
Step: Suppose you have $2n$ vertices with the desired degrees. Now add two more vertices $a$ and $b$. Attach $a$ to one of the existing ones for each different degree (that is, attach $a$ to one of the existing vertices with degree $1$, and also to one of the existing vertices with degree $2$, etc.). This means that $a$ gets connected to $n$ vertices, and thus has degree $n$, the ones that $a$ gets connected to obtain degrees $2,3,...,n+1$ respectively, and the ones $a$ does not connected to are left with degrees $1,2, ...n$. Finally, attach $a$ and $b$, so $b$ has degree $1$ and $a$ ends up with degree $n+1$. So, we have two nodes each of degrees $1,2,...n+1$, as desired to complete the inductive step.
