Problème proposé par Bernard Vignes

Deux compagnies aériennes sont consultées pour assurer la desserte de plusieurs métropoles régionales.
Le cahier des charges fixe l'objectif de créer le plus grand nombre possible de liaisons¹ qui respectent les trois conditions suivantes :
-    entre deux métropoles il y a au maximum une  liaison¹ qui est assurée par une seule compagnie,
-    une même compagnie ne peut pas réaliser un circuit passant par trois métropoles tel que m₁ ==>  m₂ ==> m₃ ==> m₁,
-    tout circuit de longueur l > 3 à bord d’un avion de la même compagnie est autorisé.
Il leur est demandé de proposer différentes variantes selon que le nombre de métropoles desservies est égal à 6, 7, 8 ou 9.
Pour chacune de ces quatre valeurs, déterminer le nombre de liaisons proposées par les deux compagnies et donner une représentation graphique de ces liaisons.

¹Nota : Une liaison est un trajet de métropole à métropole sans escale avec aller-retour par la même compagnie.