Dado un gráfico $G$ con $n$ vértices. Sea $k$ denotan el grado mínimo entre los vértices. Supongamos que $k\geq 3n/4$ . Coloreamos los bordes de $G$ en $2$ colores. Demostrar que existe un subgrafo conectado con al menos $k+1$ vértices cuyas aristas tienen el mismo color.
Desde $k$ es el grado mínimo, basta con encontrar un vértice $v$ tal que el subgrafo formado por $v$ y sus vecinos pueden conectarse utilizando aristas de un solo color.
Me resulta más fácil trabajar con la siguiente reformulación:
Tenemos un gráfico $G$ con las propiedades antes mencionadas, seleccionamos algunas aristas del grafo tales que el grafo $H$ formado por estas aristas no tiene componentes de tamaño superior a $k$ y eliminar estas aristas. Demostrar que el gráfico resultante $G'$ tiene una componente conectada de tamaño al menos $k+1$ .
Supongamos que hay un contraejemplo a esto. Supongamos que en el contraejemplo $H$ (El gráfico de las aristas eliminadas) tiene un componente conectado $K$ . Entonces obtenemos otro contraejemplo si añadimos a $H$ todas las demás aristas entre los vértices de $K$ En otras palabras, podemos eliminar aún más aristas sin dejar de satisfacer la propiedad de que $H$ no tiene componentes conectados de tamaño superior a $k$ .
Así que sólo tenemos que comprobar los casos en los que las aristas eliminadas se construyen de la siguiente manera: Tomar una partición $P_1,P_2\dots P_k$ de los vértices de $G$ tal que $|P_i|\leq k$ . Elimina todas las aristas que están entre dos vértices del mismo conjunto.
También hay que tener en cuenta que si tenemos dos conjuntos $P_i$ y $P_j$ que tienen menos gracias $k$ vértices combinados entonces podemos obtener otro contraejemplo tomando una partición muy similar a $P_1,P_2\dots P_k$ con la diferencia de que sustituimos $P_i$ y $P_j$ para $P_i\cup P_j$
Desde $k\geq\frac{3n}{4}$ Sólo tenemos que comprobar las particiones de los vértices de $G$ en dos conjuntos. ¿Por qué? En una partición de tres o más conjuntos los dos más pequeños tienen un tamaño menor o igual a $\frac{2n}{3}<\frac{3n}{4}\leq k$ por lo que podríamos obtener un contraejemplo con un conjunto menos si intercambiamos los dos conjuntos más pequeños por la unión. Así que podemos obtener un contraejemplo con dos conjuntos a partir de un contraejemplo de más de $2$ conjuntos.
En otras palabras, si hubiera un contraejemplo, también habría un contraejemplo obtenido al dividir los vértices del gráfico en dos conjuntos y eliminar las aristas entre los vértices del mismo conjunto.
Supongamos que ese contraejemplo existe realmente:
Tomamos nuestro gráfico $G$ y dividir los vértices de $G$ en dos subconjuntos de tamaño no superior a $k$ eliminamos las aristas entre vértices del mismo conjunto. El resultado es un grafo bipartito.
Supongamos que nuestro grafo bipartito es $X,Y$ con $|X|=l,|Y|=n-l$ . Entonces los vértices de $X$ tener un título al menos $k-l+1$ (ya que cada uno pierde como máximo $l-1$ aristas) y los vértices de $|Y|$ tener un título al menos $k-n+l+1$ Dado que cada uno pierde como máximo $n-l-1$ bordes. Esto nos dice que cada componente conectado tiene un tamaño de al menos $2k-n+2\geq\frac{3n}{2}-n+2=\frac{n}{2}+2$ (porque un componente conectado tiene al menos $k-l+1$ vértices en $Y$ y al menos $k-n+l+1$ vértices en $X$ ). Así que todos los componentes conectados tienen un tamaño de al menos $\frac{n}{2}+2$ Esto sólo es posible si el gráfico tiene un componente conectado.
Así que hemos probado algo ligeramente más fuerte de lo que se deseaba:
Si $G$ es un gráfico de grado mínimo $k$ con $k\geq \frac{3n}{4}$ en la que las aristas son de color azul y rojo, debe cumplirse una de las siguientes condiciones:
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
