Graphe sans triangle

[deliche]

Bonjour, j'ai un exercice sur les graphe sans triangle.
Un graphe sans triangle est un graphe qui ne contient pas de cycle de longueur 3.
On veut montrer la propriété suivante:
P(n): Pour tout graphe sans triangle à n sommets et m arêtes m
Je dois montrer que cette preuve n'en ai pas une.

On raisonne par récurrence sur n:

-si n=0 le suel graphe a n sommets est le graphe vide qui est sans triangle et a 0
arêtes don (P0) est vraie.
-Soit n tel que (Pn) est vraie et G un graphe sans triangle a n sommets . Considérons un chemin dans G .En reliant un nouveau sommet à on obtient un graphe G' sans triangle a n+1 sommets et (au plus ) aretes. Or l n donc donc G' a au plus arêtes.Donc (Pn+1) est vraie
Donc (Pn) vérifiée pour tout n.
Selon moi ce qui est faux c'est surement lorsque n0 parceque le cas n=0 ets juste. Mais je ne comprend cette partie avec .

[Ben314]

Salut,

On raisonne par récurrence sur n:
-si n=0 le suel graphe a n sommets est le graphe vide qui est sans triangle et a 0
arêtes don (P0) est vraie. <= Correct
-Soit n tel que (Pn) est vraie <= O.K : on suppose que P(n) est vrai et on doit donc montrer que P(n+1) l'est aussi.
et G un graphe sans triangle a n sommets . <= ???? Qu'est ce que ça vient foutre là ce truc ????

Ce qu'on doit montrer, c'est que P(n+1) est vrai, c'est à dire que TOUT les graphes à n+1 sommet vérifient l'inégalité, donc y'a zéro le choix, ce que l'on doit considérer c'est un graphe quelconque à n+1 sommet et surement pas un graphe à n sommets.

Et la suite du texte, ça donne UNE méthode pour, partant d'un graphe G à n sommet et sans triangles, construire UN graphe G' à n+1 sommets et sans triangles. Et il s'avère que si G vérifie l'inégalité et qu'on emploie cette méthode là pour construire G' alors G' vérifie aussi l'inégalité.
Mais ça prouve que dalle vu qu'il n'y a rien qui prouve que TOUT les graphes à n+1 sommets (et sans triangles) peuvent être obtenues à l'aide de cette méthode là.

[deliche]

Je dois aussi montrer que tout graphe sans triangle a n sommet possede (au moins) un sommet de degré inférieur ou égal a . Je me suis dit que je pouvait commencer en supposant le contraire mais je ne sais pas comment continuer.

Supposons tout graphe sans triangle a n sommets possede (aucun) sommet strictement superieur a