Teorema sobre los conjuntos independientes en un grafo G= (V,E)

Question

Me preguntaba sobre las siguientes afirmaciones equivalentes relativas a un gráfico $G(V,E)$ y un subconjunto $S \subseteq V$ :

1. S es un conjunto independiente

2. $V-S$ es una cubierta de vértices

3. S es una camarilla en el gráfico complementado $\bar{G}= (V,\bar{E})$ donde dos vértices son adyacentes si no lo son en $G$ .

Si por ejemplo considero el siguiente gráfico donde he tratado de ilustrar las afirmaciones:

Para el segundo enunciado termino con un gráfico nulo sin aristas, por lo que la cubierta de vértices es sólo el conjunto vacío en este caso?

Esto parece bastante intuitivo cuando se considera un ejemplo. Me gustaría saber cómo demostraría estas equivalencias.

Answer 1

$V\setminus S$ es un conjunto de vértices. No afecta al conjunto de aristas.

Las pruebas son más o menos directas después de escribir las definiciones. Por ejemplo, para que 1 implique 3, sea $i$ y $j$ sean vértices arbitrarios en $S$ . Por definición de conjunto independiente, $(i,j)\notin E$ . Por definición de complemento, $(i,j)\in \bar{E}$ . Porque $i$ y $j$ eran arbitrarias, hemos demostrado que $S$ es una camarilla en $\bar{G}$ .