Hola
Demuestre que \( X \) es una cobertura de vértices en un grafo \( G \) si y solo si \( V(G)\setminus X \) es un conjunto independiente. Deduzca que \( \beta(G)=n(G)-\alpha(G). \)
Hola, cómo podemos hacer este problema?
Si \( X \) es una cobertura, entonces toda arista del grafo incide en algún vértice de \( X \). Por tanto no puede haber una arista uniendo dos vértices del complementario de \( X \) y así tal conjunto complementario es un conjunto independiente.
Recíprocamente si el complementario es independiente no puede haber una arista uniendo dos vértices de tal complementario y así toda arista necesariamente incide el un vértice de \( X \). Por tanto \( X \) es una cobertura.
Para la segunda parte usa lo anterior y la definición de conjunto maximal independiente y cobertura minimal.
Como siempre:
si no te sale, concreta las dudas explicando que has intentado.
Saludos.
