Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Prove that the sequence $ \langle d_1, \cdots ,d_n \rangle$ is a graphic sequence if and only if $\langle n-d_1-1, \cdots, n-d_n -1 \rangle$ is a graphic sequence.

The theorem I am trying to apply is: " The sequence $\langle d_1 ,\cdots , d_n\rangle$ is a graphic sequence if and only if the sequence $\langle d_2-1 , \cdots ,d_{d_1 +1} -1 , \cdots ,d_n \rangle $ is a graphic sequence.

Any help?

Thank's in advance!

share|cite|improve this question
See also: Degree Sequence of the complement graph – Martin Sleziak Jun 19 '15 at 9:03
up vote 2 down vote accepted

Hint: Consider the complement of the graph.

share|cite|improve this answer
Can you expalain it a little more? It is $n - d_1 -1$ the degree of a vertex in the complement graph. – passenger Feb 29 '12 at 20:45
@passenger: I am not sure what more I can explain without giving it all away. As it is, the above can be considered a full answer, instead of just a hint. Why don't you try out some graphs, write their degree sequences, and then do the same for the complements? – Aryabhata Feb 29 '12 at 20:51
o.k I understand it , i did some graphs. It is clear now. $< n-d_1 -1 , \cdots ,n-d_n -1 >$ is the graphic sequence of the complement of $G$. Thank you for your time! – passenger Feb 29 '12 at 20:59
@passenger: You are welcome! – Aryabhata Feb 29 '12 at 21:02

Your Answer


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.