Sans fixer une definition exacte, il est difficile de prouver qu'il est polynomial ou NP-difficile.

Comme le dit Kevin, il faudrait une description un peu plus formelle pour commencer a réfléchir sur la complexité du problème : utiliser un vocabulaire plus standard, définir l'objectif d'optimisation en ces termes, et lister les contraintes (règles) précises.

Je crois comprendre sur la page indiquée que l'adversaire peut annuler un triangle en retirant un seul sommet. Dans ce cas, un objectif n'est-il pas de minimiser le nombre d’arêtes par sommet ? nombre moyen ou nombre maximal ?
Si oui, le problème est multi-objectif : on a deux objectifs contradictoires (maximiser le nombre de triangles mais minimiser le nombre d'arêtes). C'est un champ de recherche encore jeune en optimisation combinatoire, et tous les problèmes pratiques de ce type sont NP-difficiles. Un algorithme optimal pour des graphes de taille 100 (taille évoquée par vince) prendrait des heures ou des jours, sinon des mois. Cependant, il peut y avoir des heuristiques qui donneraient des solutions très satisfaisantes.