au moins deux cycles
Bonjour
Je sèche sur l'exercice suivant : Soit $G$ un graphe simple à $n$ sommets $v_1,\dots, v_n$. On note $\delta :=$ $\frac{1}{n}$ $\sum_{i=1}^n d^\circ(v_i)$. Montrer que si $\delta>2$, le graphe a au moins deux cycles.
J'ai vu que si $\delta>2$, alors $n\geq 4$ car le graphe est simple et que dans un graphe simple à 3 sommets, le degré de chaque sommet est au plus 2.
J'ai ensuite essayé de faire une récurrence sur le nombre de sommets mais sans aboutir. Je vous écris quand même ce que j'ai fait :
- pour $n=4$, les suites des degrés possibles conduisant à $\delta>2$ sont $(3,3,3,3)$ et $(3,3,2,2)$, pour chacun des deux cas, on vérifie qu'on a bien au moins deux cycles.
- supposons vrai pour $n\geq 4$ fixé. Soit $G$ un graphe à $n+1$ sommets tels que $\delta(G)>2$. Supposons que $v_n$ est le sommet de plus petit degré. Considérons alors le graphe $H$ obtenu en ôtant le sommet $v_n$ et les arêtes qui lui sont incidentes. Montrons que $\delta(H)>2$ (et après ce serait fini car les cycles de $H$ sont aussi des cycles de $G$).
Premier cas : le degré de $v_n$ dans $G$ est $\delta(G)$, alors tous les sommets de $G$ sont de degrés $\delta(G)$. Alors, dans $H$, il y a $\delta(G)$ sommets de degré $\delta(G)-1$ et $n-\delta(G)$ sommets de degrés $\delta$.
Si $\delta(G)\geq 4$, tous les sommets de $H$ sont de degré au moins $3$ donc $\delta(H)\geq 3$
Si $\delta(G)=3$, comme $n\geq 4$, il y a au moins un sommet de degré $3$ et les autres sont de degré au moins $2$, donc $\delta(H)>2$.
Deuxième cas : le degré de $v_n$ dans $G$ est $\neq \delta(G)$. Notons $d$ ce degré, alors $d<\delta(G)$. On a alors
$$
\sum_{i=1}^n d_H(v_i)=\sum_{i=1}^{n+1} d_G(v_i)-2d=(n+1)\delta(G)-2d\geq (n-1)\delta(G)
$$
et là je suis bloqué car je ne peux pas affirmer que $\frac{n-1}{n}\delta(G)>2$.
Voilà. En fait, je doute qu'on puisse aboutir par récurrence, mais je n'ai pas d'autres idées...
Merci à ceux qui voudront bien m'aider.
Je sèche sur l'exercice suivant : Soit $G$ un graphe simple à $n$ sommets $v_1,\dots, v_n$. On note $\delta :=$ $\frac{1}{n}$ $\sum_{i=1}^n d^\circ(v_i)$. Montrer que si $\delta>2$, le graphe a au moins deux cycles.
J'ai vu que si $\delta>2$, alors $n\geq 4$ car le graphe est simple et que dans un graphe simple à 3 sommets, le degré de chaque sommet est au plus 2.
J'ai ensuite essayé de faire une récurrence sur le nombre de sommets mais sans aboutir. Je vous écris quand même ce que j'ai fait :
- pour $n=4$, les suites des degrés possibles conduisant à $\delta>2$ sont $(3,3,3,3)$ et $(3,3,2,2)$, pour chacun des deux cas, on vérifie qu'on a bien au moins deux cycles.
- supposons vrai pour $n\geq 4$ fixé. Soit $G$ un graphe à $n+1$ sommets tels que $\delta(G)>2$. Supposons que $v_n$ est le sommet de plus petit degré. Considérons alors le graphe $H$ obtenu en ôtant le sommet $v_n$ et les arêtes qui lui sont incidentes. Montrons que $\delta(H)>2$ (et après ce serait fini car les cycles de $H$ sont aussi des cycles de $G$).
Premier cas : le degré de $v_n$ dans $G$ est $\delta(G)$, alors tous les sommets de $G$ sont de degrés $\delta(G)$. Alors, dans $H$, il y a $\delta(G)$ sommets de degré $\delta(G)-1$ et $n-\delta(G)$ sommets de degrés $\delta$.
Si $\delta(G)\geq 4$, tous les sommets de $H$ sont de degré au moins $3$ donc $\delta(H)\geq 3$
Si $\delta(G)=3$, comme $n\geq 4$, il y a au moins un sommet de degré $3$ et les autres sont de degré au moins $2$, donc $\delta(H)>2$.
Deuxième cas : le degré de $v_n$ dans $G$ est $\neq \delta(G)$. Notons $d$ ce degré, alors $d<\delta(G)$. On a alors
$$
\sum_{i=1}^n d_H(v_i)=\sum_{i=1}^{n+1} d_G(v_i)-2d=(n+1)\delta(G)-2d\geq (n-1)\delta(G)
$$
et là je suis bloqué car je ne peux pas affirmer que $\frac{n-1}{n}\delta(G)>2$.
Voilà. En fait, je doute qu'on puisse aboutir par récurrence, mais je n'ai pas d'autres idées...
Merci à ceux qui voudront bien m'aider.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Je ne crois pas : il pourrait y avoir des arêtes tombantes un peu partout : par exemple un cycle $C_n$ auquel on ajoute à chaque sommet une arête dont l'autre extrémité est degré 1. Il y a bien un unique cycle, mais il y a $2n$ arêtes avec $n$ sommets de degrés $3$ et $n$ sommets de degrés $1$.
Cela dit, en toute généralité, je n'arrive pas à montrer que si il y a au plus un cycle, alors la moyenne des degrés est $\leq 2$.
(Edit : j'ai corrigé le "de genre 1" qui n'était pas ce que je voulais dire, mais je crois que l'on s'était compris quand même.)
[Contenu du fichier pdf joint. AD]
En effet, c'est moi qui ai compris de travers ce que tu disais...