Número de componentes máximos de un grafo una vez eliminado un vértice cualquiera

Question

Sea $G$ sea un grafo arbitrario con $n$ nodos y $k$ componentes. Si se elimina un vértice de $G$ el número de componentes del gráfico resultante debe estar comprendido entre $\ldots$ ?

Me imaginé que en el peor de los casos el número de componentes sería $k - 1$ si el vértice eliminado era un componente en sí mismo.

Para el mejor de los casos, razoné que la eliminación de un vértice de un componente podría dividir el componente en dos (si el vértice es una especie de vértice de corte del componente), haciendo que el número total de componentes fuera igual a $k + 1$ .

Sin embargo la respuesta dada dice que el número de componentes está entre $k - 1$ y $n - 1$ . No entiendo el $n - 1$ parte. Por favor, indíqueme la dirección correcta.

Answer 1

Eliminar un solo vértice $v$ puede cortar un componente en $\deg(v)$ componentes, no sólo dos. ¿Y si el gráfico original tiene $k-1$ vértices aislados y una estrella? (Por un estrella Me refiero a un grafo bipartito completo $K_{1,m}$ para algunos $m$ .)

Answer 2

Un vértice cortado puede conectar más de dos piezas. Piensa en una estrella.

Answer 3

Tomemos un caso en el que todos los vértices están conectados a un vértice y, por lo tanto, la eliminación de este vértice dejará n-1 componente