11
$\begingroup$

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.

$\endgroup$

2 Answers 2

13
$\begingroup$

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!

$\endgroup$
2
  • $\begingroup$ This seems very logical, would an ad-hoc construction like this be counted as proof in an exam setting? $\endgroup$
    – Lucky
    Apr 21, 2019 at 6:08
  • 1
    $\begingroup$ @Lucky Dunno. Depends on your instructor, most likely. Those sort of issues are not interesting to me; I just answer questions on this website for fun. $\endgroup$
    – Nick Alger
    Apr 24, 2019 at 21:24
3
$\begingroup$

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!

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .