Graphes connexes sans point d'articulation — Les-mathematiques.net The most powerful custom community solution in the world

Graphes connexes sans point d'articulation

Modifié (October 2023) dans Combinatoire et Graphes
Bonjour.
Je considère un graphe simple non orienté, supposé connexe et sans point d'articulation. On note $n$ le nombre de sommets, et $p$ le nombre d'arêtes, et on suppose $n\geq  3$.

Je conjecture que les 3 propriétés suivantes sont vraies :
1) $p\geq n$
2) $p=n$ si, et seulement si, le graphe est un cycle
3) $p=n+1$ ssi le graphe est un cycle auquel on adjoint une chaîne élémentaire reliant deux de ses sommets.

J'arrive à prouver 1 et 2 mais j'ai peur d'avoir fait des erreurs.
Qu'en pensez-vous ? Connaissez-vous une bonne référence sur ce sujet ? Je vous remercie d'avance !
Bonne journée.

Réponses

  • Modifié (October 2023)
    Le 1) doit pouvoir se faire par récurrence. Sinon, si on connait quelques résultats de base sur les graphes, on peut faire comme suit. Pour tout graphe connexe, on a $p\geqslant n-1$, avec égalité si, et seulement si, le graphe est un arbre. Le cas $p=n-1$, ne peut se produire, car tout sommet terminal d'un arbre a pour voisin un point d'articulation.
    Pour le 2), rappelons un des premiers théorèmes de la théorie des graphes. Notons $S$ l'ensemble des sommets, et pour chaque sommet $s\in S$, notons $d_s$ son degré. Alors $\displaystyle \sum_{s\in S} d_s =2p$. 
     Supposons que $p=n$. Puisque le graphe ne peut avoir de sommet terminal, on a forcément $d_s \geqslant 2$, pour tout $s\in S$. Mais la relation $\displaystyle \sum_{s\in S} d_s =2p=2n$, donne alors $d_s =2$, pour tout $s\in S$. On peut alors conclure que le graphe est un cycle en considérant un chemin de longueur maximale dont tous les sommets sont distincts. (Je laisse les détails). On peut aussi invoquer le fait que tous les degrés étant pairs, le graphe est eulérien.
     La réciproque est évidente.
    Pour l'implication non triviale du 3), on suppose que $p=n+1$. Alors la relation entre degrés prouve que tous les sommets sont de degré $2$, sauf deux d'entre eux qui sont de degré $3$. Le graphe n'est pas eulérien, mais il possède un chemin qui relie les sommets de degré $3$ et qui passe par tous les sommets une seule fois. En inspectant la structure de ce chemin, on voit que le graphe doit avoir la forme indiquée (je laisse les détails).

     Les théorèmes sur les degrés, les arbres, les graphes eulériens se trouvent dans tout cours de base sur la théorie des graphes. Il y a par exemple des notes de Daniel Perrin disponibles sur le net.
  • Merci beaucoup!
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!