Corrigé de la caractérisation des suites graphiques

Arnaud Legrand

Date: 5 avril 2001

On rappelle qu'une suite finie d'entiers positifs $d=(d_1,,\dots,d_n)$ est dite «graphique» s'il existe un graphe dont la suite des degrés des sommets est $d$.

Théorème 1   Soit $0<d_1 \leqslant d_{2} \leqslant \ldots \leqslant d_n$ une suite d'entiers. On définit $d'_i = d_i - 1$ pour $n-d_n \leqslant i \leqslant n-1$ et $d'_i = d_i$ pour $1 \leqslant i \leqslant n-d_n-1$. Montrer que $(d_1,\ldots,d_n)$ est graphique si et seulement si $(d'_1,\ldots,d'_{n-1})$ l'est.

Preuve. Il y a deux sens à montrer:

$\boxed{\Leftarrow}$

Soit $d$ une suite telle que $d'$ est graphique. Montrons que $d$ est graphique. $d'$ correspond donc à un graphe $G'=(\{x_1,\dots,x_{n-1}\},E)$ avec $d_{G'}(x_i)=d'_i$ pour tout $i$ dans $\llbracket 1, n-1\rrbracket$. Soit $x_n$ un nouveau sommet. On va considérer le graphe $G=(\{x_1,\dots,x_{n}\},E\cup \{(x_n,x_{n-1}), (x_n,x_{n-2}), \dots , (x_n,x_{n-d_n})\})$ définit en ajoutant le nouveau sommet $x_n$ au graphe $G'$ et en le reliant aux $d_n$ sommets de plus haut degré de $G'$. On a donc $d_{G}(x_n)=d_n$ et pour tout $i$ dans $\llbracket n-d_n, n-1\rrbracket$, on a donc $d_{G}(x_i)=d_{G'}(x_i)+1=d'_i+1=d_i$. De même, pour tout $i$ dans $\llbracket 1, n-d_n-1\rrbracket$, on a $d_{G}(x_i)=d_{G'}(x_i)=d'_i=d_i$. Le graphe $G$ est donc un graphe tel que $d_{G}(x_i)=d'_i$ pour tout $i$ dans $\llbracket 1, n\rrbracket$. $d$ est donc une suite graphique.

$\boxed{\Rightarrow}$

Soit $d$ une suite graphique. Montrons que $d'$ est graphique. Soit $G=(\{x_1,\dots,x_n\},E)$ un graphe tel que $d_{G}(x_i)=d_i$ pour tout $i$ dans $\llbracket 1, n\rrbracket$. Dans la donstration précédente, on a rajouté $x_n$ et on l'a relié aux $d_n$ sommets de plus grand degré. Ici, on souhaiterait faire l'inverse, c'est à dire enlever $x_n$ et les arêtes qui le relient aux $d_n$ sommets de plus grand degré. Cependant, ces arêtes n'existent pas forcément pour tout graphe $G$ réalisant $d$. On va donc montrer qu'on peut transformer notre graphe $G$ en un graphe $\widetilde{G}$ qui réalise $d$ et tel que $x_n$ est relié à $x_{n-d_n},\dots,x_{n-1}$. Supposons que $x_n$ ne soit pas relié dans $G$ à chacun des $x_{n-d_n},\dots,x_{n-1}$. Alors comme $x_n$ est de degré $d_n$, il existe un sommet $x_k$ de $\{x_{1},\dots,x_{n-d_n-1}\}$ qui est relié à $x_n$. De même, il existe un sommet $x_j$ de $\{x_{n-d_n},\dots,x_{n-1}\}$ non relié à $x_n$. On a donc la situation suivante (les traits pleins représentant des arêtes et les traits interrompus l'inexistence d'arête).

Notons

$$A_k=\{s\in V \mid s x_k x_n \}$$

$$A_j=\{s\in V \mid s x_j \}.$$

On a $\vert A_k\vert=d_k-1$ et $\vert A_j\vert=d_j$. Or $d_k\leqslant d_j$. Donc $\vert A_j\vert>\vert A_k\vert$ et il existe donc un sommet $x_i$ relié à $x_j$ et pas à $x_k$. On a donc la situation suivante.

En considérant la situation suivante où on a remplacé $(x_n,x_k)$ par $(x_n,x_j)$ et $(x_j,x_i)$ par $(x_i,x_k)$,

on crée un nouveau graphe $\widetilde{G}= (V,(E\backslash\{(x_n,x_k),(x_j,x_i)\})\cup\{(x_n,x_j), (x_i,x_k)\})$ dont les degrés des sommets sont les mêmes que dans $G$. Donc si un des sommets $x_{n-d_n},\dots,x_{n-1}$ n'est pas touché par $x_n$, on peut transformer notre graphe de façon à ce qu'il le soit et ce, sans que les autres sommets de $x_{n-d_n},\dots,x_{n-1}$ déja reliés à $x_n$ en ``patissent''. En itérant le procédé, on se ramène donc à un graphe $\widetilde{G}=(\{x_1,\dots x_n\},\widetilde{E})$ qui réalise $d$ et tel que $x_n$ est relié à $x_{n-d_n},\dots,x_{n-1}$. Il suffit alors de vérifier que $G'=(\{x_1,\dots,x_{n-1}\},\widetilde{E}\backslash\{(x_n,x_{n-1}), (x_n,x_{n-2}), \dots , (x_n,x_{n-d_n})\})$, c'est à dire le graphe $\widetilde{G}$ auquel on enlève $x_n$, réalise $d'$.

$\qedsymbol$