3
$\begingroup$

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!

  • 0
    See also: [Degree Sequence of the complement graph](http://math.stackexchange.com/questions/1331192/degree-sequence-of-the-complement-graph)2015-06-19

1 Answers 1

2

Hint: Consider the complement of the graph.

  • 0
    Can you expalain it a little more? It is $n - d_1 -1$ the degree of a vertex in the complement graph.2012-02-29
  • 0
    @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?2012-02-29
  • 0
    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!2012-02-29
  • 0
    @passenger: You are welcome!2012-02-29