Salut,
C'est assez marrant ton truc...
Je pense que j'ai la soluce que j'ai trouvé (bien évidement) en construisant sur un coin de feuille les graphes en question pour n de 2 à 10 (histoire d'essayer de comprendre comment ça marche).
Il y a peut-être plus simple, mais en séparant les cas n pair et n impair et en regardant bien quel est le nombre qui apparait deux fois dans la liste des degrés (et en le rajoutant ce nombre dans le truc qu'on prouve par récurrence) ça a l'air de fonctionner :
On suppose qu'on a un graphe à
sommets avec
pair et tels que les degrés des
sommets soient :
(ce qui fait bien n nombres)On ajoute un sommet qu'on relie à tout ceux dont les degrés sont en rouge dans la liste çi dessus (ce qui augmente le degré en question de 1).
Ce nouveau sommet à pour degré
(=nombre d'entiers de
à
inclus) donc la nouvelle liste des degrés est :
(ce qui fait bien n+1 nombres)Puis on ajoute de nouveau un sommet qu'on relie à tout ceux dont les degrés sont en rouge dans la liste.
Ce nouveau sommet à de nouveau pour degré
(=nombre d'entiers de
à
inclus) et la liste devient :
(ce qui fait bien n+2 nombres)Et voilou...
EDIT : En fait, il y a même bien plus simple en faisant une récurrence de 2 en 2 : si tu part d'un graphe ayant la propriété demandée, que tu rajoute un premier sommet que tu relie à tout les autres puis que tu rajoute un second sommet que tu laisse isolé, ça te donne de nouveau un graphe ayant la propriété demandée. Et avec ce point de vue là, on voit même clairement que le graphe ayant la propriété demandé est unique pour un n donné.
