Graphe simple connexe

Poirex278

Est-ce qu'un graphe simple dont le nombre d'arête est m et le nombre de sommets est n est connexe si m >= n - 1 ?

Héhéhé

L'union disjointe du graphe complet $K_4$ (avec 6 arêtes et 4 sommets) et du graphe complet $K_2$ (avec 1 arête et 2 sommets) a $m = 6+1 = 7$ arêtes et $n=4+2 = 6$ sommets, donc vérifie $m \geq n-1$ mais n'est pas connexe.

Paul Broussous

On a plutôt l'implication (classique) : si un graphe simple est connexe, alors $m\geqslant n-1$, la réciproque étant fausse (comme le fait remarquer Héhéhé).

Poirex278

Merci !

Paul Broussous

@Poirex278 P.S. D'ailleurs on sait même caractériser le cas limite : un graphe connexe vérifie $n=m-1$ si, et seulement si, $m=n-1$.