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.

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

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

Any help?

Thank's in advance!

share|improve this question

1 Answer 1

up vote 1 down vote accepted

Hint: Consider the complement of the graph.

share|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

 
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.