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$

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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