Teoría de grafos - Prueba

Question

Necesito ayuda para demostrar la siguiente afirmación:

Sea G un $k$ -grafo regular con $n$ vértices y $k \geq 1$ . Demostrar que $G$ hace no tiene un conjunto independiente de tamaño superior a $\dfrac{n}{2}$ .

Se agradece mucho.

Answer 1

Si el gráfico es $1$ -regular, $n$ tiene que ser uniforme. Podemos dividir el conjunto de vértices en pares de vértices de manera que haya una arista entre los vértices de una partición. Un conjunto independiente no contiene más de un vértice de cada partición. Por lo tanto, el tamaño de un conjunto independiente no puede ser superior a $\frac{n}{2}$ .

Dejemos que $G$ ser un $k$ -gráfico regular ( $k$ es al menos $2$ ) con $n$ vértices.

Caso 1 : $k>\frac{n}{2}$

Dejemos que $X$ sea un conjunto independiente con más de $\frac{n}{2}$ vértices. Debe haber al menos $k$ vértices (de $G$ ) que no pertenecen a $X$ . Pero, $|X|+k>n$ una contradicción.

Caso 2 : $k\le \frac{n}{2}$

Si $G$ contiene un conjunto independiente de longitud $r$ entonces $G'$ (complemento de $G$ ) contiene un $r$ -como un subgrafo y viceversa. Demostramos que $G'$ no contiene un $r$ -clique donde $r>\frac{n}{2}$ . Necesitamos tener al menos tantos $E\left(T(n,\lceil \frac{n+1}{2}\rceil)\right)+1$ aristas para una camarilla de tamaño $\lceil \frac{n+1}{2}\rceil$ (donde $T(n,k)$ significa Gráfico de Turan de $n$ vértices y $k$ partes, $E(A)$ representa el número de aristas en el gráfico $A$ ). Pero, tenemos $\frac{n(n-k)}{2}\le \frac{n(n-2)}{2}$ bordes. (Podemos utilizar la estimación $E(T(n,m))\le \left( 1-\frac{1}{m} \right)\frac{n^2}{2}$ y elaborar cuidadosamente los casos en los que $n$ es par e impar para demostrar la desigualdad requerida).

Answer 2

Lo demostraría por contradicción. Supongamos que $G$ tiene un conjunto independiente $I$ tal que $|I| \geq \dfrac{n}{2}$ . Entonces ninguno de los vértices de $I$ son adyacentes por definición de un conjunto independiente. Sin embargo, cada vértice tiene un grado de al menos $1$ por lo que cada vértice es adyacente a algún otro vértice. Por lo tanto, cada vértice en $\overline{I}$ puede asignarse a $k$ vértices distintos. Esto nos da como máximo $\dfrac{k(n-2)}{2}$ bordes. Por el lema del apretón de manos, necesitamos satisfacer $2E = 2kn$ . Y así, debemos conectar los vértices en $I$ con aristas, contradiciendo la definición de conjunto independiente.