Contraintes de degrés des sommets d'un graphe | Tangente

Pour tout ensemble S = { X₁, X₂… X_n } avec X₁ > X₂… > X_n > 0, il s’agit de construire un graphe G ayant exactement X₁ + 1 sommets et tel que deg(G) = S. La construction se fait par récurrence sur le nombre n d’entiers contenus dans S.

Le cas de base est simple. Soit un ensemble composé d’un seul entier : S = {x}, avec x > 0. Considérons le graphe complet K_x+1. Chacun de ses x +1 sommets est de degré x et voisin des x autres sommets. K_x+1 répond aux attentes lorsque le cardinal de S est 1.

Pour tout ensemble S de cardinal n, on écrit S = {X₁, X₂… X_n } avec X₁ > X₂… > X_n > 0. Notre hypothèse de récurrence est qu’il existe un graphe G avec X₁ + 1 sommets et deg(G) = S. Prenons maintenant un ensemble T = {Y₁, Y₂… Y_n , Y_n+1 } quelconque de cardinal n + 1, avec Y₁ > Y₂… > Y_n > Y_n+1 > 0.

Construisons S’ = {Y₁ – Y_n+1, Y₁ – Y_n … Y₁ – Y₂ } à partir de T. On a Y₁ – Y_n+1 > Y₁ – Y_n >… > Y₁ – Y₂ > 0 ; S’ est donc un ensemble de n entiers positifs. Par hypothèse de récurrence, il existe alors un graphe H à Y₁ – Y_n+1 + 1 sommets vérifiant deg(H) = S’. Ajoutons à ce graphe H un ensemble C de Y_n+1 nouveaux sommets, sans aucune arête. Le graphe ainsi obtenu, noté H⁺, possède Y₁ – Y_n+1 + 1 + Y_n+1 = Y₁ + 1 sommets.

Pour obtenir le graphe G recherché, il suffit de considérer le complémentaire du graphe H⁺. Quelles sont les caractéristiques de G ? Comme H⁺, il a Y₁ + 1 sommets. Calculons-en les degrés. Par construction, chacun des Y_n+1 sommets de C est connecté à tous les autres sommets de G, c’est-à-dire à Y₁ voisins. G contient bien au moins un sommet de degré Y₁.

Montrons que pour tout j dans {2, 3… n+1} G contient aussi au moins un sommet de degré Y_j. Le graphe H (donc H⁺) contient au moins un sommet u de degré Y₁ – Y_j . Dans le complémentaire G, ce sommet u est voisin des Y₁ + 1 sommets sauf u lui-même et ses « anciens » Y₁ – Y_j voisins.

Le degré de u dans G est donc Y₁ + 1 – 1 – ( Y₁ – Y_j ), soit Y_j .

Pour conclure, il reste à constater que G ne contient aucun sommet ayant un degré hors de T. Le graphe G a donc bien toutes les caractéristiques demandées !

Pour tout graphe H, le complémentaire G de H est le graphe défini de la manière suivante. G possède exactement les mêmes sommets que H et, pour toute paire {u, v } de sommets, si H contient une arête entre u et v alors G n’en contient pas et si H ne contient pas cette arête alors G la contient.