Stabilité d'un graphe

$S$ est dit stable s'il n'existe aucune arrête du graphe $G$ reliant 2 sommets de $S$. Ainsi la stabilité de $G$ est $\alpha(G)= \{\mathrm{card}(S) \mid S \text{ est stable dans } G \}$.

[Pour info, alpha ne s'écrit pas avec un f. skyffer3]

Oui desolé vous avez raison ;-)

Bonjour,
On fait comme cela ?
Soit $G'=G-v$. Raisonnons par récurrence sur $\alpha(G)$.
Pour $\alpha(G')=1 \implies S_{\alpha(G')}=\{u\}$.

Si $v$ appartient à $S_{\alpha(G)}$ alors $S_{\alpha(G)}=\{u,v\} \implies \alpha(G)=2$.
Donc $\alpha(G') \geq \alpha(G)-1$.

Si $v$ n'appartient pas $S_{\alpha(G)}$ alors il existe une arrête $uv$ dans $G$ donc $\alpha(G)=0$.
Donc $\alpha(G')\geq \alpha(G)-1$.

Supposons que c'est vrai jusqu'à $n$ et démontrons que c'est vrai pour $n+1$.
On a \begin{align*}
\alpha_{(\text{n+1 sommets})}(G')&=n+1 \\
&=\alpha_{(\text{n sommets})}(G)+1 \\
&\geq (\alpha(G)-1)+1 \\
&= \alpha(G) \\
&\geq \alpha(G)-1\,.\end{align*}
D'où on a l'inégalité. C'est vrai ???

Et si on a par exemple le graphe $G-v$ est un triangle alors $\alpha(G-v)=0$ alors que $\alpha(G)=2$ donc $0\geq (2-1)$ ce qui est impossible, alors comment doit on montrer une inégalité qui n'est pas toujours vraie ?

Merci beaucoup Tonm :-)