Prove that: order of natural number $d_1 , d_2 , \ldots , d_n$ as descending is a ordering graph if and only if the order was sorted as descending $d_2-1, d_3 -1 , \ldots ,d_d -1,\ldots ,d_n$ be ordering graph. $d_d$ in sequence is d $d_1$. (arrangement=order).
Proof of a graph problem on degree sequence
0
$\begingroup$
graph-theory
-
5I'm not sure, but I think you are trying to state the [result of Hakimi for vertex degree sequences](http://en.wikipedia.org/wiki/Degree_(graph_theory)#Degree_sequence). – 2012-10-21
1 Answers
1
Hint: If you know that $d=d_1\ge d_2 \ge \dots \ge d_n$ are degrees of vertices of some graph, what can you say about degrees of the graph where the vertex of degree $d_1$ is omitted? Can you go in opposite direction, too? (I.e. can you obtain from a graph with degrees $d_1-1,\dots,d_d-1,d_{d+1},\dots,d_n$ a graph with degrees $d_1,d_2,\dots,d_n$?)
(I assume that the interpretation of your question given in this comment is correct and that the question is about Havel-Hakimi theorem.)