Demostrar que si $G$ es un $k$ -de un gráfico conectado, entonces $G \vee K_1$ es un $(k+1)$ -Gráfico de conexión

Question

Demostrar que si $G$ es un $k$ -de un gráfico conectado, entonces $G \vee K_1$ es $(k+1)$ -Gráfico de conexión

Esto es lo que tengo hasta ahora

Desde $G$ es un $k-connected$ existe un conjunto de vértices cortados $S \subset V(G)$ tal que $|S|\geq k$ y $G-S$ está desconectado.

Dejemos que $H =G \vee K_1$ para $|S| \leq k$ , $H-S$ está conectada ya que todavía hay un vértice $v\in K_1$ conectado a cada vértice $u \in G$ tal que $u \not \in S$ . Pido para $H$ para ser desconectado, necesitamos borrar $v$ también. Desde $H- (S \cap \{v\})=G-S$ , ya que $|S| \geq k$ , $|S \cap \{v\} \geq k+1$ Así que $H-(S \cap \{v\})$ está desconectado por lo que $H$ es $k+1$ gráfico conectado.

Así es como entiendo el problema, pero no sé cómo escribirlo formalmente.

Answer 1

Dejemos que $H=G\lor K_1$ y $v$ el vértice de $K_1$ en $H$ . Debemos demostrar dos cosas:

a) $H$ tiene al menos $k+2$ vértices.

b) $H$ no tiene ningún corte de vértice con un tamaño menor que $k+1$ .

a) es evidente: ya que $G$ es $k$ -conectado tiene al menos $k+1$ vértices, por lo que $H$ tiene al menos $k+2$ vértices.

Para b) argumentamos por contradicción. Supongamos que $S$ es un corte de vértices de tamaño máximo $k$ .

Caso 1: $v\in S$ . Entonces $S-v$ es un corte de vértice de $G$ de tamaño máximo $k-1$ contradiciendo la suposición de que $G$ es $k$ -conectado.

Caso 2: $v\notin S$ . Entonces cada vértice de $G-S$ es $v$ mismo, o conectado a $v$ Así que $G-S$ está conectada, contradiciendo la suposición de que $S$ es un corte de vértice.