En la teoría de grafos , se dice que un grafo no trivial G es k - vértice conectado (o k - conectado ) si tiene más de k vértices y después de eliminar menos de k vértices, el gráfico permanece conectado.
La conectividad de vértices , o simplemente conectividad , de un grafo es el k más grande para el cual el grafo es k -vértice-conectado.
Alternativamente, un gráfico incompleto tiene conectividad k si k es el tamaño del subconjunto más pequeño de vértices que, cuando se elimina, hace que el gráfico se desconecte [1] . Los gráficos completos se excluyen de la consideración porque no se pueden desconectar eliminando vértices. Un grafo completo con n vértices tiene una conexión de n − 1, como sigue de la primera definición.
Una definición equivalente es si para cualquier par de vértices de gráficos es posible encontrar k caminos que no se intersecan conectando estos vértices; consulte el teorema de Menger ( Diestel 2005 , p. 55). Esta definición tiene la misma respuesta: n − 1 para la conexión del grafo completo K n [1] .
Un grafo conexo 1 también se denomina conexo , un grafo conexo 2 se denomina doblemente conexo y un grafo conexo 3 se denomina, respectivamente, triconexo .
1- esqueletocualquier politopo convexo de dimensión k forma un gráfico conectado por vértice k ( teorema de Balinski , Balinski, 1961 ). El teorema de Steinitz parcialmente inverso establece que cualquier gráfico plano conectado por 3 vértices forma el esqueleto de un poliedro convexo .