Per ogni insieme S = { X1, X2… X*n *} con X1 > X2… > X*n * > 0, si tratta di costruire un grafo G con esattamente X1 + 1 vertici e tale che deg(G) = S. La costruzione avviene per induzione sul numero n di interi contenuti in S.
Il caso base è semplice. Sia un insieme composto da un solo intero: S = {x}, con x > 0. Consideriamo il grafo completo K*x*+1. Ciascuno dei suoi x +1 vertici ha grado x ed è adiacente agli x altri vertici. K*x*+1 soddisfa i requisiti quando la cardinalità di S è 1.
Per ogni insieme S di cardinalità n, scriviamo S = {X1, X2… X*n *} con X1 > X2… > X*n * > 0. La nostra ipotesi induttiva è che esista un grafo G con X1 + 1 vertici e deg(G) = S. Consideriamo ora un qualunque insieme T = {Y1, Y2… Y*n , Yn*+1 } di cardinalità n + 1, con Y1 > Y2… > Y*n > Yn*+1 > 0.
Costruiamo S’ = {Y1 – Y*n*+1, Y1 – Y*n *… Y1 – Y2 } a partire da T. Si ha Y1 – Y*n*+1 > Y1 – Y*n* >… > Y1 – Y2 > 0; S’ è dunque un insieme di n interi positivi. Per ipotesi induttiva, esiste allora un grafo H con Y1 – Y*n*+1 + 1 vertici tale che deg(H) = S’. Aggiungiamo a questo grafo H un insieme C di Y*n*+1 nuovi vertici, senza alcun arco. Il grafo così ottenuto, denotato H+, possiede Y1 – Y*n*+1 + 1 + Y*n*+1 = Y1 + 1 vertici.
Per ottenere il grafo G cercato, basta considerare il complemento del grafo H+. Quali sono le caratteristiche di G? Come H+, ha Y1 + 1 vertici. Calcoliamone i gradi. Per costruzione, ciascuno dei Y*n*+1 vertici di C è adiacente a tutti gli altri vertici di G, cioè a Y1 vicini. G contiene dunque almeno un vertice di grado Y1.
Dimostriamo che per ogni j in {2, 3… n+1} G contiene anch’esso almeno un vertice di grado Y*j*. Il grafo H (e quindi H+) contiene almeno un vertice u di grado Y1 – Y*j . Nel complemento G, tale vertice u* è adiacente a tutti i Y1 + 1 vertici, eccetto u stesso e i suoi «vecchi» Y1 – Y*j* vicini.
Il grado di u in G è dunque Y1 + 1 – 1 – ( Y1 – Y*j ), ossia Yj *.
Per concludere, resta da osservare che G non contiene alcun vertice il cui grado non appartenga a T. G possiede quindi tutte le caratteristiche richieste!
Il complemento di un grafo ------------------------------
Per ogni grafo H, il complemento G di H è il grafo definito come segue. G possiede esattamente gli stessi vertici di H e, per ogni coppia {u, v } di vertici, se H contiene un arco tra u e v, allora G non lo contiene, e se H non contiene tale arco, allora G lo contiene.