Prove that $(n, n, n-1, n-1, \ldots , 4, 4, 3, 3, 2, 2, 1, 1)$ is a graphic!

A sequence of non-negative integers is called graphic if there exist a graph whose degree sequence is precisely that sequence.

For example, $(1, 1, 1, 1, 1, 1)$ is a graphic since it's the degree sequence of graph

and $(3, 1, 0, 0, 0)$ is not a graphic since there is no graph with one vertex of degree 3, one vertex of degree 1, and three vertices of degree 0.

Now, the question is prove that

$$(n, n, n-1, n-1, \ldots, 4, 4, 3, 3, 2, 2, 1, 1)$$

is always a graphic.

My attempt is by construct the simple graph and find some pattern for building a larger one. Starting with $n=1$, then I try to construct $n=2$. Now, based on the result $n=2$, then again I construct for $n=3$, and so on.

But, after doing that process, I don't get at all the pattern for building such larger graph from previous graph. Everything seems randomly yet beautifully constructed. Here is my drawing process:

Please help me to prove this. Thanks before.

Solution 1:

Suppose you started with a (n,n,n-1,n-1,...,1,1) graphic, and you want to add two nodes, A and B, to it. Connect A with one of each type of node that's already there: one n-node, one n-1 node, etc all the way to one 1-node. Also connect A to B, but connect B to nothing else.

Now lets think about what just happened.

• A has n+1 edges (n from connections to the original graph, plus one from it's connection to B).
• B has 1 edge
• half of the nodes (one of each type) in the original graph got their edgecount bumped up by 1, by getting connected to A.

So now there are two 2-nodes, two 3-nodes, ..., two n-nodes from the original graph, plus B and the 1-node that was unchanged as two 1-nodes, plus A and the n-node that got bumped up as two n+1-nodes. Thus a graphic one size bigger!

Solution 2:

Yes there is an inductive procedure: Suppose $(n-1, n-1, n-2, n-2, \ldots, 2, 2, 1, 1)$ is graphic, and let the graph have vertices labeled $v_{n-1}, w_{n-1}, v_{n-2}, w_{n-2}, \ldots, v_2, w_2, v_1, w_1$, where subscripts equal degree of vertex. append two new verteces $v_0, w_0$. Now there is an easy way to add edges so that the degree list changes from $(n-1, n-1, \ldots, 1, 1, 0, 0)$ to $(n, n, \ldots, 2, 2, 1, 1)$. Each new edge must increase exactly two of the the degrees. Note, it's not necessary to show exactly what the new graph is, just that it exists. This may be where your induction got bogged down(?)

Hope this help!