Bonjour.
Je bloque sur un exercice de graphes censé être simple dont voici l'énoncé :
pour tous entiers p, s, t on note P(p, s, t) la proposition vraie si dans tout groupe de p personnes, il existe au moins s personnes qui se connaissent deux à deux ou au moins t personnes qui ne se connaissent pas deux à deux.
1) Reformuler cette définition en utilisant des graphes
J'ai pensé utiliser des graphes simples, non orientés et sans boucles où chaque sommet représente une personne et chaque arête relie deux personnes qui se connaissent.
P(p,s,t) est vraie s'il existe un graphe défini comme précédemment à p sommets avec au moins s arêtes ou si il faudrait lui ajouter t arêtes pour le rendre complet.
Je bloque à partir des questions suivantes :
2) Démontrer que pour tous entiers p et s, P(p,s,2) (sans mauvais jeu de mots) est vraie si seulement p >= s.
3) Est-ce que P(5,3,3) est vrai ? Preuve attendue.
4) Est-ce que P(6,3,3) est vrai ? Preuve attendue.
Je ne suis pas certain de ma modélisation.
Merci.
