Demostrar que dos maximales $k$ -subgrafos conectados de un grafo $G$ tienen como máximo $k-1$ vértices comunes.

Question

Supongamos que los dos subgrafos $A$ y $B$ del gráfico $G$ tal que $A \neq B$ .

Un máximo $k$ -un subgrafo conectado no será un subgrafo "adecuado" para ningún otro $k$ -subgrafo conectado. Aquí $k$ es el tamaño del corte de vértice mínimo.

¿Cómo demuestro esto por contradicción?

Answer 1

Supongamos que los dos máximos $k$ -subgrafos conectados comparten $k$ vértices. La eliminación de cualquier $k-1$ vértices a través de los dos subgráficos deja ambos subgráficos conectados y debe dejar al menos un vértice común, por lo que la unión de los subgrafos permanece conectada después de eliminar cualquier $k-1$ vértices - es $k$ -y estrictamente mayor que los dos subgrafos originales, lo que es una contradicción. Por tanto, la afirmación queda demostrada.