Graphe sans triangle
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 $\leq$ $\frac{n^2}{4}$.
Je dois montrer que tout graphe sans triangle à n sommets possede (au moins) un sommet de degré inférieur ou égal à $\frac{n}{2}$.
Je ne sais pas trop comment m'y prendre est-ce que je dois me servir de la propriété alors qu'il est marqué qu'on cherche a la montrer?
Merci
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 $\leq$ $\frac{n^2}{4}$.
Je dois montrer que tout graphe sans triangle à n sommets possede (au moins) un sommet de degré inférieur ou égal à $\frac{n}{2}$.
Je ne sais pas trop comment m'y prendre est-ce que je dois me servir de la propriété alors qu'il est marqué qu'on cherche a la montrer?
Merci
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Ici, avec le principe des tiroirs, ça a l'air de faire l'affaire.
on a n sommets et m arretes , mais comme on utilise pas les aretes je ne vois comprend pas pourquoi on devrait utiliser le principe des tiroirs
> Donc on suppose que un graphe a n sommets possedent un sommet de degre superieur a $\frac{n}{2}$.
n'est pas le contraire de:
> tout graphe sans triangle à n sommets possede (au moins) un sommet de degré inférieur ou égal à $\frac{n}{2}$..
Cordialement,
Rescassol
Caramba, encore raté !! Same player shoot again.
Cordialement,
Rescassol
Normalement c'est ca sinon je voit pas du tout
Le contraire de "au moins un" est "aucun".
Cordialement,
Rescassol
Un raisonnement par récurrence sur le nombre $n$ de sommets du graphe me semble convenir:
Soit $n > 3$ et supposons le résultat acquis pour tout graphe d'ordre $n-1$. Soit $G$ un graphe sans triangle possédant $n$ sommets et $m$ arêtes.
$1)$ Si $n$ est pair :
si le degré de chaque sommet vaut $\dfrac n2$, alors $m =\dfrac{ n^2}{4}$ et le résultat est établi.
sinon, $G$ étant sans triangle, il existe un sommet $x$ de degré inférieur ou égal à $\dfrac n2 -1$: en effet, si tous les sommets ont un degré supérieur à $\dfrac n2$, alors il en existe un sommet $a$, de degré $>\dfrac n2$. Soit $b$ un sommet adjacent à $a$ . Alors $\text{deg}(b)\geq\dfrac n2$, et $b$ possède un voisin $c$ parmi ceux de $a$ et $\{a,b,c\}$ forme un triangle, ce qui est impossible. On peut appliquer l' hypothèse de récurrence au sous-graphe $G - \{ x \}$
Alors: $m \leq \dfrac{( n - 1 ) ^2 }{4 } +\dfrac {n}{2} - 1 \leq \dfrac{ n^2}{4}$.
$2)$ Si $n$ est impair:
$G$ étant sans triangle , il possède un sommet $x$ de degré inférieur ou égal à $\dfrac {n - 1 }{2}$ et on conclut comme dans le cas précédent.