Combien de forme peut-on interconnecter?

Bonsoir tout le monde! Je vous sollicite car mon problème, bien que grandement simple au premier abord, est en fait, carrément lourd!!

Alors je suis étudiant, et pour un projet, je dois réaliser un jeu de conquête. Qui dit jeu de conquête dit gestion de ressources, de soldats, des combats, et des maps.
C'est ce dernier point qui me pose problème :
une map est représenté globalement par un certain nombre de territoire, région, partition, vous lui donnez le nom que vous voulez, avec pour lien entre eux les frontières qu'ils ont avec chacun! Jusque là me diriez vous, rien de bien méchant, un simple graphe suffit et hop basta!, le pire arrive maintenant quand on me dit que les maps peuvent être gérées aléatoirement...
vous ne voyez pas le problème? Le voici (attention il y a une gymnastique logique à faire) :

- en théorie, le nombre de frontière qu'un territoire peut avoir est illimité, (bien sur pour les besoins du jeu, ce ne sera pas le cas) et tous les territoires peuvent être connecté avec qui ils le veulent, jusque la pas de problème. Hors lorsque l'on passe à pratique, un problème se pose, je vous conseil un dessin pour visualiser la chose, le problème vient du fait qu'au delà de 5 territoires, on ne peut pas les connecter tous entre eux (qu'en gros chaque territoire puisse avoir une connexion avec tous les autres) hors, une fois cela remarqué, la représentation est rapide dans sa tête, mais en terme de code.... c'est une autre paire de manche!!!! car pour une petite map de 5 territoire c'est pas compliqué mais imaginons 16 territoires... ça se complique.

Voilà voilà, si vous avez compris le Shmilblick et que vous viens une solution je plussois que vous me la donniez!! :):)

bonne soirée a vous et je vous remercie d'avance pour votre générosité!!