théorie des graphes

[invitef9e3d1d4]

Bonjour,

j'ai un problème avec un exercice dans la matière de la théorie des graphes,en fait je ne sais pas d'où je peut commencer et quel théorème je peut utiliser:
voici l'exercice:

Soit G un graphe simple d'ordre n ayant k composantes connexes,Montrer que le nombre maximum d'arrêtes est (n-k)*(n-k+1)/2.
est ce que j'utilise la règle qu'un graphe connexe d'ordre n qui possède au moins (n-1) arrêtes et le montrer par récurrence ou quoi
et merci pour tout aide.
-----

[invite179e6258]

un graphe complet à n sommets a n(n-1)/2 arêtes. Avec ça tu dois pouvoir deviner quel est le graphe qui a le nombre d'arêtes donné par l'énoncé. Il restera à montrer que c'est bien le maximum.