Graphe

Posté par wonderwall3 wonderwall3

Formulez l'énoncé suivant en terme de graphe:
"Dans un groupe quelconque de n personnes (n supérieur ou égal à 2), il existe au moins deux personnes ayant le même nombre d'amis dans ce groupe"

Démontrez cette propriété.

Si quelqu'un est inspiré ça m'aiderait bien.
Merci Beaucoup

Posté par Aurelien_ Aurelien_

Bonjour,

Faire un raisonnement par l'absurde.
Soit a(k) le nombre d'amis de la k-ième personne du groupe (k allant de 1 à n).
[a(1) a(2) ... a(n)] est une liste de n termes.
les valeurs possibles pour les a(k) sont 0 1 ... n-1 (au minimum 0 ami, au maximum n-1 amis, puisqu'il ne peut pas être ami avec lui-même)
il y a donc n valeurs possibles pour a(k).

Cela ne nous suffit pas pour répondre puisqu'on pourrait affecter aux n a(k) les n valeurs disctinctes possibles.

- supposons qu'il existe une personne qui n'a pas d'ami, appelons cette personne k=1. On a alors a(1)=0
s'il existe une personne (autre que "1") ayant n-1 amis, alors elle sera amie avec tout le monde et en particulier avec "1". Ce qui n'est pas possible.
donc personne n'a n-1 amis.
Les valeurs permises pour les a(k) sont donc 0 1 ... n-2, ce qui signifie n-1 valeurs possibles pour n a(k)
=> il y aura au moins une valeur prise 2 fois

- supposons que personne n'a aucun ami. Alors les valeurs permises pour les a(k) sont 1 2 ... n-1, ce qui signifie n-1 valeurs possibles à affecter à n a(k)
=> il y aura au moins une valeur affectée 2 fois

CQFD