For any set S = { X1, X2… X*n *} with X1 > X2… > X*n* > 0, we shall construct a graph G with exactly X1 + 1 vertices such that deg(G) = S. The construction proceeds by induction on the number n of integers in S.
The base case is straightforward. Let S be a set containing a single integer: S = {x}, with x > 0. Consider the complete graph K*x*+1. Each of its x +1 vertices has degree x and is adjacent to the other x vertices. Thus K*x*+1 has the required properties when the cardinality of S is 1.
For any set S of cardinality n, write S = {X1, X2… X*n *}, with X1 > X2… > X*n* > 0. Our induction hypothesis is that there exists a graph G with X1 + 1 vertices and deg(G) = S. Now take any set T = {Y1, Y2… Y*n , Yn*+1 } of cardinality n + 1, with Y1 > Y2… > Y*n > Yn*+1 > 0.
From T, construct S’ = {Y1 – Y*n*+1, Y1 – Y*n *… Y1 – Y2 }. Since Y1 – Y*n*+1 > Y1 – Y*n* >… > Y1 – Y2 > 0, S’ is a set of n positive integers. By the induction hypothesis, there is therefore a graph H with Y1 – Y*n*+1 + 1 vertices such that deg(H) = S’. Add to H a set C of Y*n*+1 new vertices, with no edges. The resulting graph, denoted H+, has Y1 – Y*n*+1 + 1 + Y*n*+1 = Y1 + 1 vertices.
To obtain the graph G we seek, simply take the complement of H+. What properties does G have? Like H+, it has Y1 + 1 vertices. Let us calculate their degrees. By construction, each of the Y*n*+1 vertices in C is adjacent to every other vertex of G—that is, to Y1 vertices. Thus G does indeed contain at least one vertex of degree Y1.
Let us show that for every j in {2, 3… n+1}, G also contains at least one vertex of degree Y*j*. The graph H (and hence H+) contains at least one vertex u of degree Y1 – Y*j . In the complement G, this vertex u* is adjacent to all Y1 + 1 vertices except u itself and its Y1 – Y*j* "former" neighbors.
The degree of u in G is therefore Y1 + 1 – 1 – (Y1 – Y*j ), namely Yj *.
To complete the proof, it remains only to observe that G has no vertex whose degree lies outside T. Thus G does indeed have all the required properties!
The complement of a graph ------------------------------
For any graph H, its complement G is defined as follows. G has exactly the same vertices as H, and for every pair of vertices {u, v}, if H contains an edge between u and v, then G does not; if H does not contain that edge, then G does.