Salut,
S'il y a
sommets et que tu note
la liste des degrés avec
, des conditions nécéssaires (et je pense suffisantes) sont :
- Il faut que
(évident)
- La somme
doit être paire vu que le nombre total d'arrêtes
vérifie
- Pour tout
on doit avoir
où
est le nombre d'arrêtes (en fait, il suffit de vérifier cette inégalité pour le plus grand indice
tel que
)
Cette dernière condition vient du fait que, si on groupe les sommets en deux :
et
alors de chaque sommet
, il part au plus
arrêtes allant à un autre sommet de
donc il part au moins
arrêtes vers des sommets de
.
Il y a donc au moins
arrêtes de
vers
.
Or, des arrêtes arrivant dans
, il y en a au maximum
On doit donc avoir
, c'est à dire
.
Par exemple, pour (4,4,4,2,2), le max des
tels que
est 3 et on a
donc la configuration est impossible.
A mon avis, ces conditions sont suffisantes : je pense qu'il suffit de relier le sommet
de plus grand degrés avec les sommets (autres que
) de plus grand degrés puis de recommencer avec le nouveau sommet de plus haut degrés restant...