Degree Sequence of the complement graph Given a degree sequence say, $(3,3,4,4,4,4)$ for a graph $G$, how would you quickly find the degree sequence of its the complement? In the solutions it just gives $(1,1,1,1,2,2)$.
How does one know straight away?
 A: There are six vertices - so there are five possible edges for each vertex. If a vertex is joined to two vertices in the graph, it is joined to the other $5-2=3$ vertices in the complement.
A: First of all, you have written the degree sequence in the wrong way. We always write degree sequences in non-increasing order (descending order) so I first rewrite your given degree sequences as follows
(3,3,4,4,4,4) ⇒ (4,4,4,4,3,3)
(1,1,1,1,2,2) ⇒ (2,2,1,1,1,1)
Now, Answer to your Question-
Suppose we have a graph G and its complement G', now if we union these two graphs then we get a complete graph Kn where n is no of vertices in the given graph G.
Now We know that degree of each vertex in the complete graph Kn is (n-1)
In your given graph, there are 6 vertices so in the complete graph K6,degree of each vertex will be (n-1) = 6-1 =5
Click Here To See Image
So degree sequence of a complement of your given graph is (2,2,1,1,1,1)
In general, If we have a graph G with n vertices and its complement G' and if the degree sequence of graph G is d1,d2,d3,d4 .... ,dn then degree sequence of its complement will be (n-1)-dn,(n-1)-d[n-1].....,(n-1)-d2 ,(n-1)-d1
