Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

image of graph 1-1, 3-4, 5-6

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:

drawing process

Please help me to prove this. Thanks before.

share|improve this question

2 Answers 2

up vote 8 down vote accepted

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!

share|improve this answer

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!

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.