Un conjunto independiente es un conjunto de vértices en un gráfico, de los cuales no hay dos de los cuales son adyacentes. Sea G un grafo con n vértices y con el grado máximo igual a . Demuestre que, G contiene un conjunto independiente de tamaño al menos n/( + 1).
Respuesta
¿Demasiados anuncios?
Paul Sinclair
Puntos
6547
Para cualquier conjunto $A$ , dejemos que $\overline A = \{ x\ |\ x \in A \text{ or $ x $ is adjacent to } A\}$ . Tenga en cuenta que $$\overline A = \bigcup_{x \in A} \overline{\{x\}}$$ Ahora bien, como cualquier vértice puede tener como máximo $\Delta$ vecinos, $\left|\overline{\{x\}}\right| \le \Delta + 1$ (donde $|X|$ es la cardinalidad de $X$ ). Por lo tanto, $$\left|\overline A\right| \le \sum_{x\in A} \left|\overline{\{x\}}\right| \le \sum_{x\in A} (\Delta + 1) = |A|(\Delta + 1)$$
Si $|A| < \frac{n}{\Delta + 1}$ entonces $\left|\overline A\right| < n$ lo que significa que hay al menos un elemento $a \in G$ que no está en $\overline A$ . Si $A$ es independiente, entonces también lo es $A\cup\{a\}$ . Por lo tanto, cualquier conjunto independiente puede ampliarse hasta que el conjunto tenga al menos $\frac{n}{\Delta + 1}$ vértices independientes.
