Deje $G$ un gráfico con $n$ vértices, $\delta(G)$ es el mínimo grado de cada vértice en $G$, y deje $\kappa(G)$ ser el tamaño mínimo de las vértice cutset, o su vértice conectividad.
Mostrar que si $\delta(G) \geq n - 2$,$\kappa(G) = \delta(G)$.
Soy capaz de mostrar el caso de al $\delta(G) = n - 1$, en cuyo caso es sólo un grafo completo, y es más fácil.
Pero cuando intento hacer caso al $\delta(G) = n - 2$, soy capaz de llegar tan lejos como:
Si elegimos un vértice $v$ tal que $\deg(v)=n-2$, es que no está directamente conectada a un otro borde $w$, y del mismo modo para $w$. Esto significa que si queremos eliminar todos los vértices sino $v$$w$, se aumentaría el número de componentes conectados por 1, pero, ¿cómo puedo demostrar que este es el número mínimo para todos los $n$?
Otros pensamientos:$n > 4$, no podría ser exactamente dos vértices $v$ $w$ pero no sé cómo probar esto o encontrar un contraejemplo.
Cualquier ayuda se agradece.
