Graphe sommet-connexe
En théorie des graphes, un graphe connexe . Un graphe autre qu'un graphe complet est de degré de sommet-connexité k s'il est k-sommet-connexe sans être k+1-sommet-connexe, donc si k est la taille du plus petit sous-ensemble de sommets dont la suppression déconnecte le graphe. Les graphes complets ne sont pas inclus dans cette version de la définition car ils ne peuvent pas être déconnectés en supprimant des sommets. Le graphe complet à n sommets est de degré de connexité n-1. Une définition équivalente est qu'un graphe avec au moins deux sommets est k-sommet-connexe, pour chaque paire de ses sommets, il existe est k chaînes indépendantes reliant ces sommets ; c'est le théorème de Menger. Cette définition produit la même réponse n − 1, pour la connexité du graphe complet Kn. Un graphe 1-sommet-connexe est un appelé un graphe connexe ; un graphe 2-sommet-connexe et appelé un graphe biconnexe. Un graphe 3-connexe est aussi appelé triconnexe. Un graphe régulier de degré k est au plus k-sommet-connexe et k-arête-connexe. S'il est effectivement k-sommet-connexe et k-arête-connexe, il est dit optimalement connecté. Pour tout n, le graphe complet Kn (régulier de degré n – 1) est optimalement connecté. Pour tout k > 2 et tout j > 1, le graphe moulin Wd(k, j) est 1-sommet-connexe. Pour le séparer en j composantes connexes, il suffit de supprimer son sommet de plus haut degré : son centre. Le graphe cycle Cn est 2-sommet-connexe pour tout n > 3. Le 110-graphe de Iofinova-Ivanov est 3-sommet-connexe. Image:Biggs-Smith graph.svg|Le [[graphe de Biggs-Smith]] est 3-régulier, 3-sommet-connexe et 3-arête-connexe : il est optimalement connecté. Image:Windmill graph Wd(5,4).svg|Le [[graphe moulin]] Wd(5,4) n'est plus connexe si l'on supprime son sommet central: il est 1-sommet-connexe. Image:Complete graph K6.svg|Le [[graphe complet]] K6 est 5-sommet-connexe. Nombre de graphes simples -sommet-connexes à sommets pour de 1 à 9, avec la référence à OEIS : {| class="wikitable" |- ! \ !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7 !! 8
