Bonjour,

C’est un exercice ?
Si oui, chercher est la meilleure solution (de loin).

Remarque : pour que ce problème soit pertinent, il faut que la notion de ‘se connaître’ soit réciproque (A connait B <=> B connait A).

Piste : il peut être alors intéressant de supposer qu'il soit possible que toute personne ait un nombre distinct de connaissances au sein d’un groupe fermé de n personnes. Et regarder ce que ça impose en nombre de connaissances pour chacun… Normalement ça devrait permettre de conclure assez rapidement 😊. Un raisonnement par l’absurde est toujours une bonne idée.

On part du principe que les relations sont symétriques.

Par récurrence,

P(N) : "Pour un groupe de N personnes, il y a au moins deux personnes ayant le même nombre de relation."
P(3) est vrai.

sur un groupe de N personnes comme on a dit, chaque personne connaît de 0 à N-1 autres personnes.

Soit il existe une personne du groupe qui connaît toutes les autres, soit il n'en existe pas.

S'il n'existe pas une telle personne, le groupe comporte N personnes avec un nombre de connaissances de 0 à N-2 (soit seulement N-1 choix. Il y a donc forcément deux personnes avec le même nombre de connaissances.

S'il existe une telle personne, on peut construite un nouveau graphe en supprimant la personne et toute ses relations. Cela nous ramène au cas P(N-1).