Oui je me demandais si toutes les combinaisons n-k sont possibles (autres que les cas ou k>=n).
Je pensais partir par exemple, pour un k fixé, d'un graphe complet à (k+1) nœuds. Et d'augmenter progressivement le nombre de nœud jusqu'à avoir n nœuds. Reste à mettre au point la méthode permettant de passer d'un graphe connexe de degré k à m sommets à un graphe connexe de degré k à (m+1) sommets. Mais j'avais l'intuition que cela pouvait se faire simplement.
Après ça reste qu'une idée, c'est toi qui voit ce qui te semble le plus prometteur.

Partager